线段树模板

单点修改区间查询

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;
    }
};

区间修改区间查询

const int MAXN = 100000;
struct SegTree
{
    int sum[MAXN * 4 + 5];
    int lazy[MAXN * 4 + 5];
    // 根据子节点算当前节点
    void up(int now)
    {
        sum[now] = sum[now * 2] + sum[now * 2 + 1];
    }
    // 把当前节点的lazy传下去
    void down(int now, int l, int r)
    {
        if (lazy[now] == 0)
            return;
        int mid = (l + r) / 2;
        sum[now * 2] += (mid - l + 1) * lazy[now];
        sum[now * 2 + 1] += (r - mid) * lazy[now];
        lazy[now * 2] += lazy[now];
        lazy[now * 2 + 1] += lazy[now];
        lazy[now] = 0;
    }
    // 基于 a 数组 build
    void build(int now, int l, int r)
    {
        if (l == r)
        {
            sum[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid);
        build(now * 2 + 1, mid + 1, r);
        up(now);
    }
    // 当前节点是 now，对应区间是 l~r
    // 希望给第 x~y 个数加上 z
    void update(int now, int l, int r, int x, int y, int z)
    {
        if (x <= l && r <= y)
        {
            lazy[now] += z;
            sum[now] += (r - l + 1) * z;
            return;
        }
        int mid = (l + r) / 2;
        down(now, l, r);
        if (x <= mid)
            update(now * 2, l, mid, x, y, z);
        if (y >= mid + 1)
            update(now * 2 + 1, mid + 1, r, x, y, z);
        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;
        down(now, l, r);
        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;
    }
};

动态开点线段树（单点修改区间查询）

const int MAXN = 500000;
struct SegTree
{
    int root, tot;
    int sum[MAXN * 30 + 5];
    int lc[MAXN * 30 + 5]; // 左子节点
    int rc[MAXN * 30 + 5]; // 右子节点
    // 根据子节点算当前节点
    void up(int now)
    {
        sum[now] = sum[lc[now]] + sum[rc[now]];
    }
    // 当前节点是 now，对应区间是 l~r
    // 希望给第 x 个数加上 y
    void update(int &now, int l, int r, int x, int y)
    {
        if (now == 0)
            now = ++tot;
        if (l == r)
        {
            sum[now] += y;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid)
            update(lc[now], l, mid, x, y);
        if (x > mid)
            update(rc[now], 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 (now == 0)
            now = ++tot;
        if (x <= l && r <= y)
            return sum[now];
        int mid = (l + r) / 2;
        int res = 0;
        if (x <= mid)
            res += query(lc[now], l, mid, x, y);
        if (y >= mid + 1)
            res += query(rc[now], mid + 1, r, x, y);
        return res;
    }
};

注意空间占用，后面使用时得写 st.root 作为 now

• st.query(st.root, 1, 1'000'000'000, 1, a[i] - 1);
• st.update(st.root, 1, n, a[i], 1);