【模板】线段树（sum）

const int maxn = 100010;
int a[100010];

struct tree
{
    int a;
    int l, r;
    int tag;
    tree()
    {
        tag = 0;
        l = 0;
        r = 0;
        a = 0;
    }
}node[maxn];

inline int lc(int x)
{
    return x << 1;
}

inline int rc(int x)
{
    return x << 1 | 1;
}

void push_up_sum(int x)
{
    node[x].a = node[lc(x)].a + node[rc(x)].a;
}

void build(int x, int l, int r)
{
    node[x].l = l;
    node[x].r = r;
    if (l == r)
    {
        node[x].a = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lc(x), l, mid);
    build(rc(x), mid + 1, r);
    push_up_sum(x);
}

inline void f(int x, int k)
{
    node[x].tag += k;
    node[x].a += k * (node[x].r - node[x].l + 1);
}

inline void push_down(int x)
{
    f(lc(x), node[x].tag);
    f(rc(x), node[x].tag);
    node[x].tag = 0;
}

inline void update(int left, int right, int x, int k)
{
    if (left <= node[x].l && node[x].r <= right)
    {
        node[x].a += k * (node[x].r - node[x].l + 1);
        node[x].tag += k;
        return;
    }
    push_down(x);
    int mid = (node[x].l + node[x].r) >> 1;
    if (left <= mid) update(left, right, lc(x), k);
    if (right > mid) update(left, right, rc(x), k);
    push_up_sum(x);
}

long long int query(int left, int right, int x)
{
    long long int res = 0;
    if (left <= node[x].l && node[x].r <= right) return node[x].a;
    int mid = (node[x].l + node[x].r) >> 1;
    if (left <= mid) res += query(left, right, lc(x));
    if (right > mid) res += query(left, right, rc(x));
    return res;
}