线段树模板

单点修改区间查询

const int MAXN = 500000;
struct SegTree
{
    int sum[MAXN * 4 + 5];
    // 根据子节点算当前节点
    void up(int now)
    {
        sum[now] = sum[now * 2] + sum[now * 2 + 1];
    }
    // 基于 a 数组 build
    void build(int a[], int now, int l, int r)
    {
        if (l == r)
        {
            sum[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, now * 2, l, mid);
        build(a, now * 2 + 1, mid + 1, r);
        up(now);
    }
    // 当前节点是 now，对应区间是 l~r
    // 希望给第 x 个数加上 y
    void update(int now, int l, int r, int x, int y)
    {
        if (l == r)
        {
            sum[now] += y;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid)
            update(now * 2, l, mid, x, y);
        if (x > mid)
            update(now * 2 + 1, mid + 1, r, x, y);
        up(now);
    }
    // 当前节点是 now，对应区间是 l~r
    // 返回 x~y 在这个区间内的和
    int query(int now, int l, int r, int x, int y)
    {
        if (x <= l && r <= y)
            return sum[now];
        int mid = (l + r) / 2;
        int res = 0;
        if (x <= mid)
            res += query(now * 2, l, mid, x, y);
        if (y >= mid + 1)
            res += query(now * 2 + 1, mid + 1, r, x, y);
        return res;
    }
};