线段树 新）

ll arr[maxn], tree[maxn<<2], lazy[maxn<<2];

void build(int node, int l, int r)
{
    if(l == r) {tree[node] = arr[l]; return;}
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int l, int r, int x)
{
    if(l == r) return tree[node];
    int ans = 0, mid = (l + r) / 2;
    if(x <= mid) ans += query(node * 2, l, mid, x);
    if(x > mid) ans += query(node * 2 + 1, mid + 1, r, x);
    return ans;
}

int query(int node, int l, int r, int x, int y)
{
    if(x <= l && y >= r) return tree[node];
    int ans = 0, mid = (l + r) / 2;
    if(x <= mid) ans += query(node * 2, l, mid, x, y);
    if(y > mid) ans += query(node * 2 + 1, mid + 1, r, x, y);
    return ans;
}

void update(int node, int l, int r, int x, int c)
{
    if(l == r) {tree[node] += c; return;}
    int mid = (l + r) / 2;
    if(x <= mid) update(node * 2, l, mid, x, c);
    else update(node * 2 + 1, mid + 1, r, x, c);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void update(int node, int l, int r, int x, int y, ll c)
{
    if(l == r) {tree[node] += c; return;}
    int mid = (l + r) / 2;
    if(x <= mid) update(node * 2, l, mid, x, y, c);
    if(y > mid) update(node * 2 + 1, mid + 1, r, x, y, c);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void push_down(int node, int length)
{
    if(lazy[node])
    {
        tree[2 * node] += lazy[node] * ((length + 1) / 2);
        tree[2 * node + 1] += lazy[node] * (length / 2);
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

ll query(int node, int l, int r, int x, int y)
{
    if(x <= l && y >= r) return tree[node];
    push_down(node, r - l + 1);
    ll ans = 0L; int mid = (l + r) / 2;
    if(x <= mid) ans += query(node * 2, l, mid, x, y);
    if(y > mid) ans += query(node * 2 + 1, mid + 1, r, x, y);
    return ans;
}

void update(int node, int l, int r, int x, int y, ll c)
{
    if(x <= l && y >= r)
    {
        tree[node] += (r - l + 1) * c;
        lazy[node] += c;
        return;
    }
    push_down(node, r - l + 1);
    int mid = (l + r) / 2;
    if(x <= mid) update(node * 2, l, mid, x, y, c);
    if(y > mid) update(node * 2 + 1, mid + 1, r, x, y, c);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}