大型线段树 - 知识点梳理
可持久化线段树
可持久化数据结构可以通过不断重复利用节点，在高效且省空间的情况下建立及存储普通数据结构的多个历史版本并进行查询。因为存在时间轴，因此有时可搭配离线算法使用。
实现方法
所有树形数据结构的可持久化处理都和这个差不多
普通的线段树长这样：
假设要对其中一个节点进行修改并建立一个历史版本，朴素的做法是新建立这样一棵树，然后修改一条链上的节点。
这时就能发现一个事实：只有被修改的这条链上的节点发生了变化，其他的节点根本没有发生变化，因此最好不再建一遍。这就是可持久化的本质：尽量重复利用已经建好的节点，新建立最少的节点构成一个新的版本。
我们把不会变的节点的边连向原树上的节点，然后：（如果你平时写普通线段树不习惯动态开点，记住这要写动态开点）
可以看到新的树只有一条链的节点是新建的，形态与原树完全一样。
这样就达到了最大化利用已建好节点的目的。每条链长约 \(\log n\)，因此可持久化线段树空间复杂度为 \(O(n + m\log n)\)，时间复杂度为 \(O((n + m)\log n)\)。（朴素算法为 \(O(mn)\)）
例题：Luogu P3919 【模板】可持久化线段树 1（可持久化数组）
不知道这题为什么没有区间查询。
上代码！
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int cnt, sum[25 * MAXN], n, m, son[25 * MAXN][2], root[MAXN], a[MAXN];
int build (int tl, int tr) {
int cur = ++cnt;
if (tl != tr) {
int mid = (tl + tr) >> 1;
son[cur][0] = build (tl, mid);
son[cur][1] = build (mid + 1, tr);
sum[cur] = sum[son[cur][0]] + sum[son[cur][1]];
}
else sum[cur] = a[tl];
return cur;
}
int modify (int pre, int tl, int tr, int p, int x) {
int cur = ++cnt;
son[cur][0] = son[pre][0];
son[cur][1] = son[pre][1];
sum[cur] = sum[pre];
if (tl == tr) {
sum[cur] = x;
}
else {
int mid = (tl + tr) >> 1;
if (p <= mid) son[cur][0] = modify (son[pre][0], tl, mid, p, x);
else son[cur][1] = modify (son[pre][1], mid + 1, tr, p, x);
sum[cur] = sum[son[cur][0]] + sum[son[cur][1]];
}
return cur;
}
int query (int cur, int tl, int tr, int p) {
if (tl == tr) return sum[cur];
else {
int mid = (tl + tr) >> 1;
if (p <= mid) return query (son[cur][0], tl, mid, p);
else return query (son[cur][1], mid + 1, tr, p);
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
root[0] = build (1, n);
int v, loc, val, op;
for (int i = 1;i <= m;i++) {
cin >> v >> op;
if (op == 1) {
cin >> loc >> val;
root[i] = modify (root[v], 1, n, loc, val);
}
else {
cin >> loc;
cout << query (root[v], 1, n, loc) << endl;
root[i] = root[v];
}
}
return 0;
}
常见优化
以可持久化数组搭载其他数据结构
例题：Luogu P3402 可持久化并查集
普通并查集使用 father 数组存储元素所在集合，我们可以将 father 数组可持久化，回滚版本时直接回滚数组的版本即可。
注意：可持久化线段树不能直接修改节点，否则会影响前面的版本，要修改节点只能新建一条链！所以这道题没法写路径压缩优化。这道题按秩合并或者按深度合并都可。
注意：一定不要忘记可持久化线段树需要开 \(\log n\) 倍空间，所以有时简单将任意数据结构的数组全部可持久化得到可持久化的数据结构不可行！（e. g. 不要尝试这样写可持久化平衡树）
上代码！
#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005, MAXM = 2e5 + 5;
int cnt, fa[55 * MAXN], dep[55 * MAXN], n, m, son[55 * MAXN][2], root[MAXM];
int build (int tl, int tr) {
int cur = ++cnt;
if (tl != tr) {
int mid = (tl + tr) >> 1;
son[cur][0] = build (tl, mid);
son[cur][1] = build (mid + 1, tr);
}
else {
fa[cur] = tl;
dep[cur] = 1;
}
return cur;
}
int modifydep (int pre, int tl, int tr, int p, int x) {
int cur = ++cnt;
son[cur][0] = son[pre][0];
son[cur][1] = son[pre][1];
dep[cur] = dep[pre];
fa[cur] = fa[pre];
if (tl == tr) {
dep[cur] = x;
}
else {
int mid = (tl + tr) >> 1;
if (p <= mid) son[cur][0] = modifydep (son[pre][0], tl, mid, p, x);
else son[cur][1] = modifydep (son[pre][1], mid + 1, tr, p, x);
}
return cur;
}
int modifyfa (int pre, int tl, int tr, int p, int x) {
int cur = ++cnt;
son[cur][0] = son[pre][0];
son[cur][1] = son[pre][1];
dep[cur] = dep[pre];
fa[cur] = fa[pre];
if (tl == tr) {
fa[cur] = x;
}
else {
int mid = (tl + tr) >> 1;
if (p <= mid) son[cur][0] = modifyfa (son[pre][0], tl, mid, p, x);
else son[cur][1] = modifyfa (son[pre][1], mid + 1, tr, p, x);
}
return cur;
}
int querydep (int cur, int tl, int tr, int p) {
if (tl == tr) return dep[cur];
else {
int mid = (tl + tr) >> 1;
if (p <= mid) return querydep (son[cur][0], tl, mid, p);
else return querydep (son[cur][1], mid + 1, tr, p);
}
}
int queryfa (int cur, int tl, int tr, int p) {
if (tl == tr) return fa[cur];
else {
int mid = (tl + tr) >> 1;
if (p <= mid) return queryfa (son[cur][0], tl, mid, p);
else return queryfa (son[cur][1], mid + 1, tr, p);
}
}
int find (int v, int x) {
int fx = queryfa (root[v], 1, n, x);
return fx == x ? x : find (v, fx);
}
void merge (int pv, int cv, int x, int y) {
int fx = find(pv, x), fy = find(pv, y);
if (fx == fy) {
root[cv] = root[pv];
return;
}
int sx = querydep (root[pv], 1, n, fx), sy = querydep (root[pv], 1, n, fy);
if (sx > sy) swap(fx, fy), swap(sx, sy);
root[m + 1] = modifyfa (root[pv], 1, n, fx, fy);
root[cv] = modifydep (root[m + 1], 1, n, fy, max(sy, sx + 1));
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
root[0] = build (1, n);
int op, a, b, k;
for (int i = 1;i <= m;i++) {
cin >> op;
if (op == 1) {
cin >> a >> b;
merge (i - 1, i, a, b);
}
else if (op == 2) {
cin >> k;
root[i] = root[k];
}
else {
cin >> a >> b;
cout << (find (i - 1, a) == find (i - 1, b) ? 1 : 0) << endl;
root[i] = root[i - 1];
}
}
return 0;
}
离线算法
作为一种可持久化数据结构，可以维护时间轴。
例题：Luogu P3834 【模板】可持久化线段树 2 我知道这不是离线，但原理一样的
我们可以将数组下标抽象为时间轴，以此来建版本，用可持久化线段树维护桶的前缀和（即第 \(i\) 个版本的 \(sum_j\) 表示 \(a_{1\dots i}\) 中 \(j\) 出现的次数）。
查询时我们将两个版本的数据相减就得到了 \(a_{l\dots r}\) 中每个数的出现次数，线段树上二分即可。
上代码屎山
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005, MAXM = 200005;
struct node {
node *ls, *rs;
int lb, rb, sum;
node () {
sum = lb = rb = 0;
ls = rs = NULL;
}
};
node *build(int lb, int rb) {
node *newnode = new node;
newnode -> lb = lb;
newnode -> rb = rb;
if (lb != rb) {
int mid = (lb + rb) >> 1;
newnode -> ls = build(lb, mid);
newnode -> rs = build(mid+1, rb);
}
return newnode;
}
node *modify (node *base, int p, int x) {
node *cur = new node;
(*cur) = (*base);
cur -> sum += x;
if (cur -> lb != cur -> rb) {
int mid = (cur -> lb + cur -> rb) >> 1;
if (p <= mid) {
cur -> ls = modify (base -> ls, p, x);
}
else cur -> rs = modify (base -> rs, p, x);
}
return cur;
}
int query (node *lr, node *rr, int k) {
if (lr -> lb == lr -> rb) return lr -> lb;
else {
int lct = rr -> ls -> sum - lr -> ls -> sum;
if (lct < k) {
return query (lr -> rs, rr -> rs, k - lct);
}
else return query (lr -> ls, rr -> ls, k);
}
}
int n, m, a[MAXN], b[MAXN];
node *root[MAXN];
int main () {
cin >> n >> m;
for (int i = 1;i <= n;i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b+1, b+n+1);
int l = unique(b+1, b+n+1) - b - 1;
for (int i = 1;i <= n;i++) a[i] = lower_bound(b+1, b+l+1, a[i]) - b;
root[0] = build(1, n);
for (int i = 1;i <= n;i++) root[i] = modify(root[i - 1], a[i], 1);
int lb, rb, k;
while (m--) {
cin >> lb >> rb >> k;
cout << b[query(root[lb - 1], root[rb], k)] << endl;
}
return 0;
}
总结
可持久化线段树是很多可持久化数据结构的基础，常用于在其上方搭载其他可持久化数据结构。也常用于辅助基于时间轴的离线算法。
例题
Luogu P1972 [SDOI2009] HH的项链
\(\bf\color{red}{Luogu\ P2617\ Dynamic\ Rankings}\)
Luogu P4216 [SCOI2015] 情报传递
Luogu P7357 「PMOI-1」中位数