数据结构经典模型：线段树（一）

线段树经典模型

Kingdom UVALive4730

class segTree {
public:
    struct node {
        int l, r;
        int sum1, sum2;
        int tag1, tag2;

        void apply1(int v) {
            tag1 += v;
            sum1 += v * (r-l+1);
        }
        void apply2(int v) {
            tag2 += v;
            sum2 += v * (r-l+1);
        }
    };

    inline void push(int p) {
        if (t[p].l != t[p].r && t[p].tag1) {
            t[p<<1].apply1(t[p].tag1);
            t[p<<1 | 1].apply1(t[p].tag1);
            t[p].tag1 = 0;
        }
        if (t[p].l != t[p].r && t[p].tag2) {
            t[p<<1].apply2(t[p].tag2);
            t[p<<1 | 1].apply2(t[p].tag2);
            t[p].tag2 = 0;
        }
    }
    inline void pull(int p) {
        int lc = p<<1, rc = p<<1 | 1;
        t[p].sum1 = t[lc].sum1 + t[rc].sum1;
        t[p].sum2 = t[lc].sum2 + t[rc].sum2;
    }

    void change(int p, const int l, const int r, int add1, int add2) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].apply1(add1), t[p].apply2(add2);
            return;
        }

        push(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p<<1, l, r, add1, add2);
        if (r > mid) change(p<<1 | 1, l, r, add1, add2);

        pull(p);
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l >= r) return;
        int mid = (l+r) >> 1;
        if (l <= mid) build(p<<1, l, mid);
        if (r > mid) build(p<<1 | 1, mid+1, r);
    }

    void query(int p, const int C) {
        if (t[p].l == t[p].r) {
            printf("%d %d\n", t[p].sum1, t[p].sum2);
            return;
        }
        push(p);

        int mid = (t[p].l + t[p].r) >> 1;
        if (C <= mid) query(p<<1, C);
        else query(p<<1 | 1, C);
    }

    int n;
    vector<node> t;

    segTree() = default;
    segTree(int _n) : n(_n) {
        assert(n > 0);
        t.resize(n << 2);
    }
    void clear() {
        fill(t.begin(), t.end(), node());
    }
};

int R, n;
const int maxn = 100000 + 10, inf = 0x3f3f3f3f;
int cnt[maxn], pa[maxn], ymax[maxn], ymin[maxn];
typedef pair<int, int> PII;
PII a[maxn];
segTree seg(maxn);

void init() {
    seg.clear();
    for (int i = 0; i < maxn; i++) pa[i] = i;
    memset(cnt, 0, sizeof cnt);
    memset(ymax, 0, sizeof ymax);
    memset(ymin, inf, sizeof ymin);
}

int get(int x) {
    return pa[x] == x ? x : pa[x] = get(pa[x]);
}

void prework(int R) {
    seg.build(1, 0, R);
    for (int i = 0; i < n; i++) seg.change(1, a[i].second, a[i].second, 1, 1);
}

void solve(int R) {
    int m;
    scanf("%d", &m);
    while (m--) {
        char str[5];
        scanf("%s", str);
        if (str[0] == 'r') {
            int A, B;
            scanf("%d%d", &A, &B);
            A = get(A), B = get(B);
            if (A == B) continue;

            seg.change(1, ymin[B], ymax[B], -1, -cnt[B]);
            seg.change(1, ymin[A], ymax[A], -1, -cnt[A]);

            pa[B] = A, cnt[A] += cnt[B];
            ymin[A] = min(ymin[A], ymin[B]), ymax[A] = max(ymax[A], ymax[B]);
            seg.change(1, ymin[A], ymax[A], 1, cnt[A]);
        }
        else {
            double _C;
            scanf("%lf", &_C);
            int C = _C * 2;

            if (C > R) puts("0 0");
            else seg.query(1, C);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        init();
        scanf("%d", &n);
        R = 0;
        for (int i = 0; i < n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            y <<= 1;
            R = max(R, y);
            a[i] = {x, y};
            ymax[i] = ymin[i] = y;
            cnt[i] = 1;
        }

        prework(R);
        solve(R);
    }
}

可持久化权值线段树

区间第 k 小

下面来看一种特殊的线段树，即权值线段树
权值线段树经常用于处理区间第 $k$ 小的问题中
假设序列 $A = \{a_1, a_2, \cdots , a_n\} = \{-2, -6, 12, 3\}$

• 先将序列离散化成 $\{2， 1， 4， 3\}$，来看一下如何用线段树找第 $k$ 小

• $\textbf{for} \ \forall i \in [1, n]$，对每个 $i$ 都建立一棵表示区间 $[1, i]$ 的线段树
  在每个 $i$ 上查询区间 $[1, i]$ 的第 $k$ 小，复杂度是 $O(\log n)$
  从前往后扫描序列 $[1, n]$，对于第 $i$ 棵线段树，我们可以将第 $i-1$ 棵线段树复制过来，然后再修改
  

• 对于第 $i$ 棵线段树和第 $j$ 棵线段树 $(i < j)$，二者的拓扑结构完全一样，唯一的区别就是每个点的权值不同
  由于节点权值为： 节点表示的区间 $[l, r]$ 中有多少个元素？
  由前缀和思想，对于询问区间 $[L, R]$，$tree(R) - tree(L-1)$ 就表示 $[L, R]$ 中有多少个元素
  $tree(P) = tree(R)-tree(L-1)$ 仍然为一棵线段树，每个节点的拓扑结构不变，权值相减

• 这样就等于在 $tree(P)$ 上找第 $k$ 小，利用二分思想

  • 如果 $tree(P).left$ 中元素个数 $\geqslant K$，递归在 $tree(P).left$ 中找第 $K$ 小
  • 否则，令 $K' = K-cnt(tree(P).left)$，在 $tree(P).right$ 中找第 $K'$ 小

对上述线段树进行可持久化
综上分析可以发现，算法的时间复杂度非常好，但是空间复杂度是 $O(n^2)$
观察这几棵线段树发现，实际上第 $i$ 棵线段树与第 $i-1$ 棵线段树比
只有加粗的部分不一样，剩下的都一样，加粗部分路径即发生修改的路径，
我们只要存储修改路径上的节点就可以了，如下图所示

重要的细节
为了方便定位到每一棵线段树，需要建立一个 $root[\cdots]$ 数组
记录第 $i$ 棵线段树根节点的编号（或者说是数组地址）

K-th number
第 K 大数

细节，主席树执行单点修改的时候，是基于历史版本 $pre$
$\textbf{change}(pre, l, r, x), \ t[pre]$ 表示历史版本 $pre$ 的根节点
$t[pre]$ 表示的区间对应于 $[l, r]$，令 $mid \leftarrow (l+r)/2$

• $t[t_{pre}.l]$ 对应于区间 $[l, mid]$
• $t[t_{pre}.r]$ 对应于区间 $[mid+1, r]$

主席树执行单点修改

• 新建一个第 $i$ 阶段版本的新根节点 $t[i]$，基于旧版本 $pre$ 的根节点，对第 $i$ 阶段的新根节点进行修改
  $t[pre] \xrightarrow{\text{update}: \ f(P)} t[i]$，执行 $f(P)$ 操作
• 自顶向下递归历史版本的线段树，递归对 $t_{pre}$ 的子树进行修改
  • 如果 $x \leqslant mid$，那么基于历史版本 $t[t_{pre}.l]$，对区间 $[l, mid]$ 执行 $f(P)$ 操作，并且建立新节点 $u$
    递归返回新节点编号 $u$，并且令 $t[i].l = u$
  • 如果 $x > mid$，基于历史版本 $t[t_{pre}.r]$ 修改区间 $[mid+1, r]$ 并且建立新节点 $u$
    递归返回，令 $t[i].r = u$

主席树查询区间 $[u, v]$ 第 $k$ 小，利用前缀和思想，令 $u \leftarrow u-1, v \leftarrow v$
考虑 $t[u]$ 和 $t[v]$ 这两棵线段树

• 注意到版本 $u$ 表示的线段树 $t[u]$ 和版本 $v$ 表示的线段树 $t[v]$ ，对区间的划分是相同的
  都表示区间 $[1\cdots n]$，因为我们是从前往后遍历，在区间中执行单点增加
  • $t[u]$ 这棵线段树，表示区间是 $[1\cdots u] \cup [u+1 \cdots n]$
    实际上我们只统计了 $[1\cdots u]$ 的信息，对于 $[u \cdots n]$ 中的点，其权值为 $0$
    所以 $t[u]$ 这棵线段树，等价于存储了 $[1\cdots u]$ 区间内一共有多少个点
    其表示的区间为 $[l, r] = [1, n]$（对于 $[u+1, n]$ 中的点，其权值为 $0$，因为在版本 $u$ 并未添加 $u$ 之后的点）
  • 同理，$t[v]$ 这棵线段树存储了 $[1\cdots v]$ 区间内一共有多少个点
    $x = t[v] - t[u]$ 表示区间 $[u+1, v]$ 中一共有 $x$ 个点
    （实际上根节点表示的区间一般仍然为 $[1, n]$，只不过 $v$ 之后的点并没有添加，所以 $[v+1, n]$ 的权值为 $0$）
• $x = t_v.sum - t_u.sum$ 表示区间 $[u+1, v]$ 中有 $x$ 个数，那么第 $k$ 小可以用二分思想解决
  由于这两个版本的线段树对于区间的划分完全一致，所以同时递归这两棵线段树
  这两棵线段树根节点表示区间为 $[l, r]=[1,n], \ mid = (l+r)/2$
  根节点的地址为 $u = root(u-1), v = root(v)\quad query(u, v, l, r, K):$
  (是 $u-1$ 不是 $u$，因为我们询问区间 $[u, v]$)
  • $t[t_u.l], \ t[t_v.l]$ 表示区间 $[l, mid]$, 其中的元素个数为 $cnt = t[t_v.l].sum - t[t_u.l].sum$
    如果 $K \leqslant cnt$，同时递归左子树，$query(t_u.l, \ t_v.l, \ l, mid, K)$
  • $t[t_u.r], t[t_v.r]$ 表示区间 $[mid+1, r]$，如果 $K > cnt$，那么同时递归右子树
    在右子树中找到第 $K - cnt$ 小的元素，$query(t_u.r,\ t_v.r, \ mid+1, r, K-cnt)$

class wsegTree {
public:
    struct node {
        int l, r;
        int sum;
    };

    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n << 5);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int build(int l, int r) {
        int u = ++tot;
        if (l >= r) return u;
        int mid = (l + r) >> 1;
        t[u].l = build(l, mid);
        t[u].r = build(mid+1, r);
        return u;
    }

    int change(int pre, int l, int r, int x) {
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum = t[pre].sum + 1;
        if (l >= r) return u;

        int mid = (l + r) >> 1;
        if (x <= mid) t[u].l = change(t[pre].l, l, mid, x);
        else t[u].r = change(t[pre].r, mid + 1, r, x);

        return u;
    }

    int query(int u, int v, int l, int r, int K) {
        if (l == r) return l;
        int cnt = t[t[v].l].sum - t[t[u].l].sum;
        int mid = (l + r) >> 1;

        if (K <= cnt) return query(t[u].l, t[v].l, l, mid, K);
        else return query(t[u].r, t[v].r, mid+1, r, K-cnt);
    }
};

const int maxn = 100000 + 10;
wsegTree wseg(maxn);
int n, m, root[maxn], a[maxn], b[maxn];

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    map<int, int> M;
    int idx = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), M[a[i]] = 0;
    for (auto &x : M) {
        x.second = ++idx, b[idx] = x.first;
    }

    for (int i = 1; i <= n; i++) {
        root[i] = wseg.change(root[i-1], 1, idx, M[a[i]]);
    }

    while (m--) {
        int u, v, k;
        scanf("%d%d%d", &u, &v, &k);
        int res = wseg.query(root[u-1], root[v], 1, idx, k);
        printf("%d\n", b[res]);
    }
}

区间内小于等于 k 的数有多少

HDU4417
Super Mario

class wsegTree {
public:
    struct node {
        int l, r;
        int sum;
    };

    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n * 20);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int build(int l, int r) {
        int u = ++tot;
        if (l >= r) return u;
        int mid = (l + r) >> 1;
        t[u].l = build(l, mid);
        t[u].r = build(mid+1, r);
        return u;
    }

    int change(int pre, int l, int r, int x, int v) {
        // find [l, r] = [x, x]
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum = t[pre].sum + v;
        if (l >= r) return u;
        int mid = (l + r) >> 1;
        if (x <= mid)  t[u].l = change(t[pre].l, l, mid, x, v);
        else t[u].r = change(t[pre].r, mid+1, r, x, v);
        return u;
    }
    int query(int i, int j, int l, int r, int k) {
        if (l >= r) return t[j].sum - t[i].sum;
        int res = 0, mid = (l + r) >> 1;
        if (k <= mid) res = query(t[i].l, t[j].l, l, mid, k);
        else {
            res += t[t[j].l].sum - t[t[i].l].sum;
            res += query(t[i].r, t[j].r, mid + 1, r, k);
        }
        return res;
    }
};

const int maxn = 100000 + 5;
wsegTree wseg(maxn);
int a[maxn], b[maxn], n, m, root[maxn];

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    int kase = 0;
    while (T--) {
        printf("Case %d:\n", ++kase);
        wseg.clear();
        memset(root, 0, sizeof root);
        scanf("%d%d", &n, &m);
        map<int, int> M;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]), M[a[i]] = 0;
        int idx = 0;
        for (auto &x : M) {
            x.second = ++idx, b[idx] = x.first;
        }

        // build weight segment tree
        for (int i = 1; i <= n; i++) root[i] = wseg.change(root[i-1], 1, idx, M[a[i]], 1);

        // then solve
        while (m--) {
            int u, v, h;
            scanf("%d%d%d", &u, &v, &h);
            u++, v++;
            int k = upper_bound(b+1, b+1+idx, h) - b;
            k--;
            if (k == 0) {
                puts("0");
                continue;
            }
            int res = wseg.query(root[u-1], root[v], 1, idx, k);
            printf("%d\n", res);
        }
    }
}

统计区间有多少不同数字

Sequence 2
HDU5919

给定序列 $\{a_1, a_2, \cdots , a_n\}$

• 询问区间 $[L, R]$ 中有 $k$ 个不同的数，并且求第 $\lceil \frac{k}{2} \rceil$ 大，很容易想到用主席树维护
  对于 $a_i$，主席树 $root(i)$ 表示区间 $[1\cdots i]$ 中有多少个不同的数
• 主席数叶子节点分别为 $[1, 1], [2, 2], \cdots, [n, n]$
• 问题是，要求每个数只能出现一次，不能重复计数，并且每个数只记录第一次出现的位置
  结合线段树可以单调修改的特性，可以设计出如下算法
  • 从 $n \to 1$ 倒序循环序列，并且使用一个 $\textbf{map}$ 来维护每一个数出现的位置
    对于某个 $i$，如果 $\textbf{map}[a_i] > 0$，那么不需要往主席树中添加出现次数
    否则的话，$\textbf{map}[a_i] = 0$，执行主席树单点增加 $root(i) \leftarrow \textbf{change}(root(i+1), i, 1)$
    然后令 $\textbf{map}[a_i] = i$
    （类似于树状数组单点增加，在下标为 $i$ 的位置，让权值 $+1$)
  • 还有一个问题，题中要求维护第一次出现的位置，这其实也很好解决
    对于某个位置 $i$，若 $j = \textbf{map}[a_i] > 0$，对于主席树 $root(i)$，在下标为 $j$ 的位置 $-1$ 即可
    具体来说，$root(i) \leftarrow \textbf{change}(root(i+1), i, 1)$，然后 $root(i) \leftarrow \textbf{change}(root(i), j, -1)$
    最后更改 $\textbf{map}[a_i] \leftarrow i$
• 对于每个询问，查询 $[L, R]$ 中有多少个不同的元素，对于主席树 $root(L)$，它不含有区间 $[1\cdots L-1]$ 的信息
  而只包括区间 $[L, n]$ 的信息，具体来说，对于主席树 $root(L)$，它的根节点表示区间为 $[1, n] = [L, n]$
  在主席树 $root(L)$ 上执行标准的线段树查询区间和，找到表示 $[L, R]$ 区间的节点
  返回节点维护的信息 $K=sum$ 即可
• 如何求第 $\lceil K/2 \rceil$ 个元素？只要在主席树 $root(L)$ 中执行二分即可
  具体来说，$\textbf{query}(root(L), 1, n, \lceil K/2 \rceil)$
  左子树元素个数 $\geqslant K$，递归左子树，否则递归查询右子树的第 $K-cnt$ 个元素
  • 细节，这里对主席树 $root(L)$ 根节点区间 $[1, n] = [L, n]$ 递归即可
    不必考虑 $[L, R] \subseteq [L, n]$，因为 $[L, R]$ 总共才 $K$ 个元素
    查询第 $\lceil K/2 \rceil$ 个元素，不会用到 $[R+1\cdots n]$ 这些数

另外，本例不需要对序列进行离散化，什么时候需要什么时候不需要呢？

• 对于区间第 $K$ 大，对于 $A_i$，实际上我们执行了 $C[A_i] += 1$ 的操作
  相当于第 $i$ 个主席树，叶节点 $[l, r] = [A_i, A_i]$ 处 $+1$
  表示 $A_i$ 这个数，在 $A[1\cdots i]$ 前缀序列中，出现了 $1$ 次
  我们的目的是询问部分和：其中 $A_i < A_j, \ \sum (C[A_i, A_i] \to C[A_j, A_j])$ 恰好等于 $K$ 的 $j$
  每一个叶节点表示 $[A_i, A_i]$，需要离散化
• 本例呢？本例统计的是有多少个数
  具体来说，对于某个位置 $i$，$A_i$ 第一次出现 （之前的位置 $j < i, A_i$ 都没出现过）
  我们认为 $i$ 这个位置对答案贡献了 $1$，在 $[l, r] = [i, i]$ 处 $+1$
  叶节点表示位置信息 $[i, i]$，不需要离散化

const int maxn = 200000 + 10;
int a[maxn], n, m, root[maxn];

class wsegTree {
public:
    struct node {
        int l, r;
        int sum;
    };
    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n * 36);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int change(int pre, int l, int r, int x, int v) {
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum = t[pre].sum + v;

        if (l >= r) return u;
        int mid = (l + r) >> 1;
        if (x <= mid) t[u].l = change(t[pre].l, l, mid, x, v);
        else t[u].r = change(t[pre].r, mid+1, r, x, v);

        return u;
    }

    int query(int u, int l, int r, const int li, const int ri) {
        if (li <= l && r <= ri) return t[u].sum;
        int mid = (l + r) >> 1;
        int ans = 0;
        if (li <= mid) ans += query(t[u].l, l, mid, li, ri);
        if (ri > mid) ans += query(t[u].r, mid+1, r, li, ri);
        return ans;
    }

    int query(int u, int l, int r, int k) {
        if (l >= r) return l;
        int mid = (l + r) >> 1;
        int cnt = t[t[u].l].sum;

        if (cnt >= k) return query(t[u].l, l, mid, k);
        else return query(t[u].r, mid+1, r, k-cnt);
    }
};

wsegTree wseg(maxn);

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    int kase = 0;
    while (T--) {
        printf("Case #%d:", ++kase);
        // init
        memset(root, 0, sizeof root);
        wseg.clear();

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        // build seg tree
        map<int, int> M;
        for (int i = n; i >= 1; i--) {
            root[i] = wseg.change(root[i+1], 1, n, i, 1);
            if (M[a[i]]) root[i] = wseg.change(root[i], 1, n, M[a[i]], -1);
            M[a[i]] = i;
        }

        // query
        vector<int> ans(maxn, 0);
        for (int i = 1; i <= m; i++) {
            int l, r, li, ri;
            scanf("%d%d", &l, &r);
            li = min((l + ans[i-1]) % n + 1 , (r + ans[i-1]) % n + 1);
            ri = max((l + ans[i-1]) % n + 1 , (r + ans[i-1]) % n + 1);
            if (li > ri) swap(li, ri);

            int k = wseg.query(root[li], 1, n, li, ri);
            k = (k+1) / 2;
            ans[i] = wseg.query(root[li], 1, n, k);
        }
        for (int i = 1; i <= m; i++) printf(" %d", ans[i]);
        puts("");
    }
}

延迟标记永久化

• 普通线段树，对于 $\textbf{change}(L, R, d)$，即将 $[L, R]$ 区间的数都加上 $d$，用延迟标记
  首先找到表示 $[L, R]$ 区间的节点 $u$，然后修改 $u$ 的 $dat$ 信息，并且打上延迟标记
  打上延迟标记意味着区间已经修改，但延迟标记尚未下传
  具体点说，如果之后询问子区间 $[l, r] \subset [L, R]$，必须先 $\textbf{push}(u)$
  $\textbf{push}$ 的过程就是将延迟标记作用于经过的子节点，即 $apply(u) \quad u \in \text{child path}$
  这样在递归访问子节点的时候，路径上经过的区间都会得到修改，直到问询区间 $[l, r]$
• 权值线段树，可以考虑将 $\text{lazy}$ 标记持久化，考虑到权值线段树 $\textbf{change}$ 的操作是自顶向下修改
  主席树执行 $\textbf{change}(L, R, d)$ 的时候，从 $[1, n] \to \cdots \to [L, R]$ 路径上所有点表示的区间都会改变
  于是可以边递归边修改，对于路径 $[1, n] \to \cdots \to [L, R]$ 的所有点 $u$
  都执行 $u.\text{dat} += d \cdot (\min(u_r, R)-\max(u_l, L) + 1)$
  只要在递归终点，要修改的区间 $[L, R]$ 打上 $\text{lazy}$ 标记
  注意，此时的状态是
  $[1, n] \to [L, R]$，包括 $[L, R]$ 所有区间都已经修改完毕，但延迟标记尚未下传到 $[L, R]$ 的子区间中
• 如果 $[L, R]$ 有 $\text{lazy}$ 标记，当且仅当询问子区间 $[li, ri] \subset [L, R]$ 的时候，才下传延迟标记
  这里可以在递归的时候，加入一个参数 $add$
  $\textbf{query}(u, li, ri, add)$，初始调用的时候 $add = 0, \textbf{query}(u, 1, n, 0)$
  • 如果 $li \leqslant u_l \leqslant u_r \leqslant ri$，$u$ 这个节点就为待求区间
    $res \leftarrow u.\text{dat} + add \cdot (u_r - u_l + 1)$
  • 否则的话，需要递归求解 $u$ 的子区间，令 $add \leftarrow add + u.\text{lazy}$
    然后考虑递归左半边和右半边，以左半边为例，$res += \textbf{query}(t[u].l, \ li, ri, add + u.\text{lazy})$

HDU4348
To The Moon

• 在时间 $t = 0$ 建一棵线段树，$root(0) = build(1, n)$，建树时候将叶节点数据初始化为 $a_i$
• 接下来根据时间 $t$ 建主席树，$(C \ L \ R \ d)$ 实际上就是 $root_t = \textbf{change}(root_{t-1}, l, r, d)$ 操作
• 对于询问 $(Q \ L \ R)$，直接在当前时间点 $root(t)$ 执行查询，历史时间点就查询 $root(t')$
• $(B \ t)$，清空时间 $t$ 以后的操作，只要把动态开点的指针 $tot \leftarrow root(t+1)$ 即可
  或者将当前的时间戳设为 $t$， $t_{\text{cur}} \leftarrow t$

const int maxn = 1e5 + 10;
int n, m, root[maxn];
ll a[maxn];

class wsegTree {
public:
    struct node {
        int l, r;
        ll lazy, sum;
    };
    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n * 25);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int build(int l, int r) {
        int u = ++tot;
        if (l >= r) {
            t[u].sum = a[l];
            return u;
        }
        int mid = (l + r) >> 1;
        t[u].l = build(l, mid);
        t[u].r = build(mid+1, r);
        t[u].sum = t[t[u].l].sum + t[t[u].r].sum;
        return u;
    }

    int change(int pre, int l, int r, const int li, const int ri, ll v) {
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum += v * (min(r, ri) - max(l, li) + 1);

        if (li <= l && r <= ri) {
            t[u].lazy += v;
            return u;
        }

        int mid = (l + r) >> 1;
        if (li <= mid) t[u].l = change(t[pre].l, l, mid, li, ri, v);
        if (ri > mid) t[u].r = change(t[pre].r, mid+1, r, li, ri, v);

        return u;
    }

    ll query(int u, int l, int r, const int li, const int ri, ll add) {
        if (li <= l && r <= ri) {
            ll res = t[u].sum + add * (r-l+1);
            return res;
        }
        add += t[u].lazy;
        int mid = (l + r) >> 1;
        ll res = 0;
        if (li <= mid) res += query(t[u].l, l, mid, li, ri, add);
        if (ri > mid) res += query(t[u].r, mid+1, r, li, ri, add);
        return res;
    }
};

wsegTree wseg(maxn);

int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d%d", &n, &m)) {
        // init
        wseg.clear();
        memset(root, 0, sizeof root);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

        // build
        root[0] = wseg.build(1, n);
        // m queries
        int t = 0;
        while (m--) {
            char str[2];
            scanf("%s", str);

            if (str[0] == 'Q') {
                int li, ri;
                scanf("%d%d", &li, &ri);
                //debug(li);
                ll res = wseg.query(root[t], 1, n, li, ri, 0);
                printf("%lld\n", res);
            }
            if (str[0] == 'C') {
                t++;
                int li, ri;
                ll d;
                scanf("%d%d%lld", &li, &ri, &d);
                root[t] = wseg.change(root[t-1], 1, n, li, ri, d);
            }
            if (str[0] == 'H') {
                int li, ri, ti;
                scanf("%d%d%d", &li, &ri, &ti);
                ll res = wseg.query(root[ti], 1, n, li, ri, 0);
                printf("%lld\n", res);
            }
            if (str[0] == 'B') {
                int ti;
                scanf("%d", &ti);
                t = ti;
            }
        }
    }
}

主席树树上查询

树上查询常见的问题，给你树上任意两个节点 $u, v$，问询 $u \to v$ 路径上第 $k$ 小节点是谁？权值多少？
Count On a Tree
SPOJ-COT

令 $\text{lca} = \text{LCA}(u, v),\ pa = pa(lca)$
$f(u, li, ri)$ 表示从 $\text{root}$ 到 $u$ 的路径上，权值落在 $[li, ri]$ 区间内的点的个数
$u \to v$ 路径上，权值落在区间 $[li, ri]$ 的点的个数为

$$f(v, li, ri) + f(u, li, ri) - f(pa, li, ri) - f(\text{lca}, li, ri)$$

可以考虑使用主席树（函数式线段树）来维护

• 先对所有的权值进行离散化，编号为 $u$ 的点，离散后的权值为 $M[a_u]$

• 设根节点为 $1$，哨兵节点为 $0$，$\textbf{dfs}(u, pa)$ 遍历树，初始调用 $\textbf{dfs}(1, 0)$

• 在 $\textbf{dfs}(u, pa)$ 的时候，$\text{root}(u) \leftarrow \textbf{change}(\text{root}(pa), M[a_u], 1)$

• 接下来就是在路径序列中执行 KQuery，对于主席树的某个节点 $[p_l, p_r]$，它包含权值在 $[u, v]$ 区间内的点的个数为

  • 同时递归 $\text{root}(v), \text{root}(u), \text{root}(\text{lca}), \text{root}(pa)$ 四棵线段树
    找到表示 $[p_l, p_r]$ 的节点 $t[u], t[v], t[\text{lca}], t[pa]$
  • $\text{cnt}(p) = t[v].sum + t[u].sum - t[\text{lca}].sum - t[pa].sum$

  然后就是标准的二分查找，如果 $\text{cnt}(t_p.l) \geqslant K$，查询 $p$ 的左子树，否则查询右子树第 $K-\text{cnt}(t_p.l)$ 个元素
  直到叶节点 $l = r$，返回 $l$

class Graph {
public:
    int tot = 1;
    int n;
    vector<int> head, ver, ne;

    Graph() = default;
    Graph(int _n) : n(_n) {
        tot = 1;
        head.resize(n), ver.resize(n<<1), ne.resize(n<<1);
    }
    void clear() {
        tot = 1;
        fill(head.begin(), head.end(), 0);
    }
    void add(int a, int b) {
        ver[++tot] = b, ne[tot] = head[a], head[a] = tot;
    }
};

const int maxn = 100000 + 10;
const int LOG = 31;
int idx, m, a[maxn], b[maxn], root[maxn], dep[maxn], f[maxn][LOG+1];
map<int, int> M;
Graph G(maxn);
int n = 0;

class wsegTree {
public:
    struct node {
        int l, r;
        int sum;
    };
    int n;
    int tot;
    vector<node> t;

    wsegTree() = default;
    wsegTree(int _n) : n(_n) {
        assert(n > 0);
        tot = 0;
        t.resize(n << 5);
    }
    void clear() {
        tot = 0;
        fill(t.begin(), t.end(), node());
    }

    int change(int pre, int l, int r, int x, int v) {
        int u = ++tot;
        t[u] = t[pre];
        t[u].sum = t[pre].sum + v;

        if (l >= r) return u;
        int mid = (l + r) >> 1;
        if (x <= mid) t[u].l = change(t[pre].l, l, mid, x, v);
        else t[u].r = change(t[pre].r, mid+1, r, x, v);

        return u;
    }

    int query(int u, int v, int lca, int fa, int l, int r, int k) {
        if (l >= r) return l;

        int cnt = t[t[u].l].sum + t[t[v].l].sum - t[t[lca].l].sum - t[t[fa].l].sum;
        int mid = (l + r) >> 1;
        if (cnt >= k) return query(t[u].l, t[v].l, t[lca].l, t[fa].l, l, mid, k);
        else return query(t[u].r, t[v].r, t[lca].r, t[fa].r, mid+1, r, k-cnt);
    }
};

wsegTree wseg(maxn);

void dfs(int u, int pa) {
    f[u][0] = pa, dep[u] = dep[pa] + 1;
    for (int j = 1; j <= LOG; j++) f[u][j] = f[f[u][j-1]][j-1];
    root[u] = wseg.change(root[pa], 1, n, M[a[u]], 1);

    for (int i = G.head[u]; i; i = G.ne[i]) {
        int v = G.ver[i];
        if (v == pa) continue;
        dfs(v, u);
    }
}

int LCA(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    for (int i = LOG; i >= 0; i--) {
        if (dep[f[y][i]] >= dep[x]) y = f[y][i];
    }
    if (y == x) return y;
    for (int i = LOG; i >= 0; i--) {
        if (f[y][i] != f[x][i]) y = f[y][i], x = f[x][i];
    }
    return f[x][0];
}

int main() {
    freopen("input.txt", "r", stdin);
    memset(root, 0, sizeof root);
    memset(dep, 0, sizeof dep);
    memset(f, 0, sizeof f);
    M.clear();
    // get graph
    scanf("%d%d", &idx, &m);
    for (int i = 1; i <= idx; i++) scanf("%d", &a[i]), M[a[i]] = 0;

    n = 0;
    for (auto &u : M) {
        u.second = ++n, b[n] = u.first;
    }

    for (int i = 1; i <= idx-1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.add(u, v), G.add(v, u);
    }

    // dfs
    dfs(1, 0);

    // query
    int res = 0;
    while (m--) {
        int u, v, k;
        scanf("%d%d%d", &u, &v, &k);
        int lca = LCA(u, v), fa = f[lca][0];
        //debug(fa);
        int res = wseg.query(root[u], root[v], root[lca], root[fa], 1, n, k);
        printf("%d\n", b[res]);
    }
}