专栏文章

可持久化线段树 / 主席树

GGrace2022
算法·理论参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
2 份
快照标识符
@miexbx77
此快照首次捕获于
2025/11/26 02:43
3 个月前
此快照最后确认于
2025/12/01 21:27
3 个月前
查看原文
初学者对该类数据结构的评价：思维难度：55；代码难度：55；应用难度：+∞+\infty；调试难度：未知未知。
本文的每一个知识点都遵循“原理-实现-相关题目/拓展”的顺序讲解，不提供完整代码。若按照目录从前往后阅读本文，并独立写出完整代码，您将学会可持久化线段树的模板和较为基础的应用。较为进阶和困难的应用不被包含在本文。
在学习该数据结构前，您需要会写普通线段树和线段树的动态开点。

可持久化数组

你需要维护这样的一个长度为 nn 的数组 aa，支持如下两种操作：
  1. 在版本 vv 的基础上，将 apa_p 修改为 cc。
  2. 输出版本 vv 中 apa_p 的值。
此外，mm 次操作中的每一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 11 开始编号，版本 00 表示初始状态数组）。
对于操作 22，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。
1≤n,m≤106 1 \leq n, m \leq {10}^6；1≤p≤n1 \leq p \leq n；设当前是第 xx 次操作，0≤v<x0 \leq v < x；−109≤ai,c≤109-{10}^9 \leq a_i,c \leq {10}^9。
一个比较自然的暴力做法，是定义一个数组 bi,jb_{i, j} 表示版本 ii 下标为 jj 的 aa 数组的值，虽然时间是 O(1)O(1) 的，但是空间是 O(nm)O(nm) 的，显然超出空间限制。
可以发现每一个版本实际上只修改一个值，完全没有必要把整个数组都复制下来。
我们依照版本与数组的映射关系建一棵版本树，以版本编号为对应版本树的根节点：
我们希望对所有没被修改的节点建立一个父亲节点，这样“版本 2”只用连两次边了：
这样的区间连边难以 O(1)O(1) 实现，但是可以通过线段树 O(log⁡n)O(\log n) 实现！
区间连没有修改的位置，相当于在原版本的基础上新建与修改位置相关的节点。
画出线段树就是：
如果要访问版本 1，就从版本 1 的根往下递归，单点查询；如果要访问版本 2，同理，此时的线段树相当于这样：
至此，我们就完成了可持久化数组的两个操作。时空复杂度都大概是 O(nlog⁡n+mlog⁡n)O(n \log n + m \log n)。
由于这里会新建节点，左右儿子指向不同的节点，所以不能用堆式存储法 rt×2rt \times 2 和 rt×2+1rt \times 2 + 1 存左右儿子，而应该动态开点。设线段树总节点数为 cntdcntd，每个节点信息为 lsls、rsrs、valval 分别表示节点的左右儿子和权值，其中只有叶子节点 valval 才有值。
设版本 ii 的根节点为 rootiroot_i，我们要在版本 vv 的基础上修改 apa_p 为 cc 成为版本 ii。
首先构建初始状态：Build(root[0], 1, n);。
需要构建一棵完整的线段树（对应图中的版本 1），包括每个节点左右儿子和叶子节点对应 aa 数组的权值：
CPP
void Build(int &rt, int l, int r){
	rt = ++cntd;
	if(l == r){
		tree[rt].val = a[l];
		return;
	}
	int mid = l + r >> 1;
	Build(tree[rt].ls, l, mid);
	Build(tree[rt].rs, mid + 1, r);
}
接着是单点修改。按照普通线段树的单点修改流程，当前递归到的根节点 rtrt 即为与修改位置 pp 相关的节点。
首先需要把版本 vv 的节点信息复制到版本 ii 上：tree[版本 i 的 rt] = tree[版本 v 的 rt];，由于这里我写的 Update 函数传的参就是原版本节点编号、返回值是现版本节点编号，所以有 tree[++cntd] = tree[rt]; rt = cntd;，最后在函数结束前 return rt;。调用：root[i] = Update(p, c, root[v], 1, n);
接着往正确方向递归，并修改对应节点信息即可。
CPP
inline int Clone(int rt){
	++cntd;
	tree[cntd] = tree[rt];
	return cntd;
}
int Update(int L, int C, int rt, int l, int r){
	rt = Clone(rt);
	if(l == r){
		tree[rt].val = C;
		return rt;
	}
	int mid = l + r >> 1;
	if(L <= mid) tree[rt].ls = Update(L, C, tree[rt].ls, l, mid);
	else tree[rt].rs = Update(L, C, tree[rt].rs, mid + 1, r);
	return rt;
}
最后是单点查询，与普通线段树代码无异，只需要在调用的时候从对应版本的根开始递归即可：Query(L, root[i], 1, n)。
注意线段树数组要开够，如果嫌计算空间麻烦建议至少开到 25×n2^5 \times n，即 tree[N << 5]，当然有的题目卡空间、有的题目可能因为多次 Update 开到更大，具体情况具体分析。
请完成 P3919 【模板】可持久化线段树 1（可持久化数组）。
可持久化数组还有离线做法，这里简单讲一下。
注意到版本 ii 是依托于版本 vv 的，以所有版本建立节点，连一条从 vv 指向 ii 的边，于是就形成了一棵树。从根节点版本 00 开始 dfs，每遍历到一个节点就执行对应操作（该修改修改，该查询那个数组记录当前版本的答案），回溯时还原，最后输出答案数组即可。因为两个毫无关系的版本一定不成父子关系，不会互相影响。
时间复杂度 O(m)O(m)，空间复杂度 O(n)O(n)。
这个思想其实有一点线段树分治的味道了，特别是学习了下一节可持久化并查集离线做法中的可撤销并查集后。感兴趣的读者可以自行学习^^

可持久化并查集

给定 nn 个集合，第 ii 个集合内初始状态下只有一个数，为 ii。
有 mm 次操作。操作分为 33 种：
  • 1 a b 合并 a,ba,b 所在集合；
  • 2 k 回到第 kk 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态，保证已经进行过至少 kk 次操作（不算本次操作），特别的，若 k=0k=0，则表示回到初始状态；
  • 3 a b 询问 a,ba,b 是否属于同一集合，如果是则输出 11，否则输出 00。
1≤n≤1051\le n\le 10^5，1≤m≤2×1051\le m\le 2\times 10^5，1≤a,b≤n1 \le a, b \le n。
可持久化并查集其实是可持久化数组的运用。
注意到并查集对 u,vu, v 的合并操作实际上是令 fau=vfa_u = v，而查询操作也与 fafa 数组的值有关。对应到可持久化数组上，fafa 数组其实就是待修改的 aa 数组。那么查询祖先节点 find(u)\text{find}(u) 相当于每次 Query 一下 faufa_u 的值，直到 fau=ufa_u = u。
这里的合并不能路径压缩，只能选择按秩合并中的按树高 depdep 合并或按子树大小 szsz 合并，也不能随机化合并。如果不理解，请重新学习并查集的原理与时间复杂度证明，或者看看这篇题解 by chenxinyang2006。
以按子树大小 szsz 合并为例，我们线段树节点需要维护两个信息 fafa 和 szsz。可以只建一棵线段树，合并时分别 Update 更新，查询祖先 Query 时打包成一个结构体返回；也可以 fafa 和 szsz 建两棵线段树分别更新查询。
对于前者，两次更新可能会导致我们一个版本建两次 log⁡n\log n 个新节点。这是没问题的，空间开大一点即可。当然，你也可以保存一个时间点标记 laslas，在第一次修改前：las=cntdlas = cntd，在每次新建节点 Clone(rt); 前判断 rt <= las 来判断是否是原版本、是否需要加新点。这篇题解 by 王鲲鹏 专门讲了这个点。
这个东西的实现是需要一定的代码能力与调试能力的。但是，不试试怎么知道你能不能一遍 AC 呢？
可持久化并查集仍有离线做法。
与可持久化数组类似，以版本编号为节点，以版本间的依赖关系建边，从版本 0 开始 dfs，进入一个节点就操作，退出一个节点就还原。
这里的还原需要用到可撤销并查集。由于 dfs 的过程本质就是一个递归栈，用一个栈存储每一次改变的 fafa 和 szsz。在函数开头存储递归前栈的大小 befbef，在函数结尾挨个弹出还原，直到栈的大小与 befbef 相等：
CPP
while(can.size() != bef){
  int u = can.top().u, v = can.top().v;
  can.pop();
  fa[u] = u; //我的习惯是将 u 合并到 v 上
  sz[v] -= sz[u];
}
根据可撤销并查集的原理，显然不能通过路径压缩合并破坏并查集结构，而需要按秩合并。这里我用的按子树大小合并。
请完成 P3402 【模板】可持久化并查集。
众所周知，并查集最简单广泛的应用就是连通性相关问题。
而有些题目会问在一些限制条件下，与连通性相关的问题。比如给图中的边赋一个权值 hh，限制为 h≤ph \le p 。
如果题目允许离线，可以直接对边排序，hh 的答案在 h−1h - 1 作新的并查集合并即可。
但是如果题目强制在线，我们可以把“版本 ii”定义为限制 h≤ih \le i 下的并查集情况，版本 ii 的更新依托于版本 i−1i - 1，用可持久化并查集实现即可。
请完成 P4768 [NOI2018] 归程，注意此题强制在线。
我都提示到这儿了，你不会还不会做吧？

可持久化权值线段树

给定 nn 个整数构成的序列 aa，mm 次查询，每次查询闭区间 [L,R][L, R] 内的第 kk 小值。
1≤n,m≤2×1051 \leq n,m \leq 2\times 10^5，0≤ai≤1090\le a_i \leq 10^9，1≤L≤R≤n1 \leq L \leq R \leq n，1≤k≤R−L+11 \leq k \leq R - L + 1。
该类静态区间求 kk 小值的问题，做法有很多：莫队/分块、整体二分、线段树合并、划分树、树状数组、Wavelet Tree……蒟蒻不会，蒟蒻瑟瑟发抖，蒟蒻只会主席树。
回忆区间 [1,n][1, n] 的 kk 小值怎么求，这是权值线段树的基础应用。以值域为“下标”，统计值为 aia_i 在序列里的个数。找到第一个前缀和 ≥k\ge k 的线段树叶子节点，其所对应的值就是 kk 小值。
区间 [L,R][L, R] 的 kk 小值是一样的，统计值为 aia_i 在 [L,R][L, R] 里的个数。后面步骤一样。
注意到“统计值为 aia_i 在 [L,R][L, R] 里的个数”，相当于求区间求和，由此想到前缀和。我们可以以某种方法，记录下 [1,L−1][1, L - 1] 和 [1,R][1, R] 的个数和，然后相减即可。
因为 [1,i][1, i] 的个数和是在 [1,i−1][1, i - 1] 的基础上加上 aia_i 的贡献，“某种方法”就是可持久化权值线段树。版本 ii 表示 a[1,i]a[1, i] 所对应的权值线段树，初始版本 00 是一棵空树。
这样，权值区间 [l,r][l, r]，数组区间 [L,R][L, R]，[1,L−1][1, L - 1] 对应的线段树节点为 uu，[1,R][1, R] 对应版的线段树节点为 vv，所对应的个数 sum=treev−treeusum = tree_{v} - tree_{u}。递归求值即可。
所以，求 kk 小值的本质就是，在线段树上找到满足条件的个数和。只不过普通权值线段树的节点区间 [l,r][l, r] 所对应的个数是直接存在线段树节点里的，而可持久化权值线段树需要通过前缀和相减计算。
CPP
int Query(int x, int u, int v, int l, int r){
	if(l == r) return p[l];
	int mid = l + r >> 1, sum = tree[tree[v].ls].cnt - tree[tree[u].ls].cnt;
	if(x <= sum) return Query(x, tree[u].ls, tree[v].ls, l, mid);
	else return Query(x - sum, tree[u].rs, tree[v].rs, mid + 1, r);
}
可持久化权值线段树是动态开点的，且初始状态是空树。也就是说无需 Build，也可以不离散化，不过要根据题目的条件与时空限制定论。
请完成 P3834 【模板】可持久化线段树 2、P1533 可怜的狗狗。
树上区间 kk 小是一样的。把版本 ii 的定义改成从根到节点 ii 的节点对应的权值线段树。sum[u,v]=treeu+treev−treelca(u,v)−treefalca(u,v)sum_{[u, v]} = tree_u + tree_v - tree_{lca(u, v)} - tree_{fa_{lca(u, v)}}。递归的时候传 4 个根即可。
请完成 P2633 Count on a tree，此题强制在线。
其实只要是权值线段树能做的，且需要区间权值线段树查询的，都可以用可持久化权值线段树做。这部分题就稍微有点难了，因为需要转化，看出此题需要用可持久化线段树。建议从头思考题目，而不是思考“此题怎么用主席树做”。
请完成 P3567 [POI 2014] KUR-Couriers、P4587 [FJOI2016] 神秘数。
题解：P4587 [FJOI2016] 神秘数

题意

给定长度为 nn 的正整数序列 aa，mm 次询问，每次询问包含两个参数 l,rl,r，求由 a[l,r]a[l, r] 所组成的可重集合的“最小不能被其子集和表示出来的正整数”。1≤n,m≤1051\le n,m\le {10}^5，∑a≤109\sum a\le {10}^9。

思路

设 a[l,r]a[l, r] 已从小到大排序，a[1,p−1]a[1, p - 1] 可以表示出 [1,q][1, q]。当前考虑 apa_p（ap>ap−1a_p \gt a_{p - 1}，取等的情况在 ap−1a_{p - 1} 考虑）：
  • ap≤q−1a_p \le q - 1，此时 apa_p 新表示出 [ap+1,ap+q][a_p + 1, a_p + q]，a[1,p]a[1, p] 可以表示出 [1,q+ap][1, q + a_p]。
  • ap>q−1a_p \gt q - 1，此时 q−1q-1 就是答案。
也就是说，apa_p 满足不会产生答案的条件是 ap−1<ap≤q−1a_{p - 1} \lt a_p \le q - 1。如果有多个 apa_p，qq 更新为 q+∑apq + \sum a_p。
设 mx=ap−1mx = a_{p - 1}，qq 为上述含义，那么对于 a[l,r]a[l, r] 值域上的值，每次贡献都有 q←q+∑[mx+1,q−1]q \gets q + \sum[mx + 1, q - 1]，注意这里的区间是 a[l,r]a[l, r] 值域上的区间，加的是区间内 aa 值的总和。当没有产生新贡献时，即 q←q+0q \gets q + 0 时，答案即为 q+1q + 1。
根据 mxmx 的定义，每一轮更新 mxmx，都有 mx←q+1mx \gets q + 1，这里的 qq 时这一轮更新前的 qq。而 qq 的更新所用到的 mxmx 也是这一轮更新前的 mxmx。
初始 mx=0mx = 0，q=0q = 0。
初看非常之抽象、难以理解，但仔细想想还是能想明白的。这里给出这部分的代码：
CPP
int l, r, mx = 0, q = 0, sum;
read(l), read(r);
while(1){
	sum = getsum(mx + 1, q + 1, root[r], root[l - 1], 1, V);
	if(sum == 0){
		write(q + 1); putchar('\n');
		break;
	}
	mx = q + 1;
	q += sum;
}
计算 ∑[mx+1,q−1]\sum[mx + 1, q - 1] 的部分（代码中的 getsum() 函数）可以用可持久化权值线段树实现。
观察 qq 的更新，会发现这相当于值域倍增的过程。所以总时间复杂度 O(m×log⁡2(∑ai)×log⁡n)O(m \times \log ^ 2(\sum a_i) \times \log n)。
完整代码CPP
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
	T s = 0; int st = 1; char c = getchar();
	while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();}
	while(c >= '0' && c <= '9'){s = (s << 3) +(s << 1) + (c ^ 48); c = getchar();}
	x = s * st;
}
template<typename T> inline void write(T x){
	if(x <0) x= -x, putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
#define LL long long
#define PII pair<int, int>
const int N = 1e5 + 5, V = 1e9;
struct node{
	int ls, rs, cnt, sum;
}tree[N << 5];
int cntd;
int a[N], root[N];
int Update(int L, int rt, int l, int r){
	++cntd; tree[cntd] = tree[rt]; rt = cntd;
	if(l == r){
		++tree[rt].cnt;
		tree[rt].sum += L;
		return rt;
	}
	int mid = l + r >> 1;
	if(L <= mid) tree[rt].ls = Update(L, tree[rt].ls, l, mid);
	else tree[rt].rs = Update(L, tree[rt].rs, mid + 1, r);
	tree[rt].cnt = tree[tree[rt].ls].cnt + tree[tree[rt].rs].cnt;
	tree[rt].sum = tree[tree[rt].ls].sum + tree[tree[rt].rs].sum;
	return rt;
}
int Query(int L, int R, int u, int v, int l, int r){
	if(u == 0 && v == 0 || u == 0) return 0;
//	cerr << L << ' ' <<R << ' ' <<l << ' ' << r << ": " << tree[u].cnt - tree[v].cnt << endl;
	if(L <= l && r <= R) return tree[u].cnt - tree[v].cnt;
	int mid = l + r >> 1, Ans = 0;
	if(L <= mid) Ans += Query(L, R, tree[u].ls, tree[v].ls, l, mid);
	if(mid < R) Ans += Query(L, R, tree[u].rs, tree[v].rs, mid + 1, r);
	return Ans;
}
int getsum(int L, int R, int u, int v, int l, int r){
//	cerr << L << ' ' << R << ": " << l << ' ' << r << ' ' << tree[u].sum - tree[v].sum << ' ' << u << endl;
	if(u == 0) return 0;
	if(L <= l && r <= R){
		return tree[u].sum - tree[v].sum;
	}
	int mid = l + r >> 1, Ans = 0;
	if(L <= mid) Ans += getsum(L, R, tree[u].ls, tree[v].ls, l, mid);
	if(mid < R) Ans += getsum(L, R, tree[u].rs, tree[v].rs, mid + 1, r);
	return Ans;
}
int main(){
	int n, m;
	read(n);
	for(int i = 1; i <= n; ++i){
		read(a[i]);
		root[i] = Update(a[i], root[i - 1], 1, V);
	}
	read(m);
	for(int i = 1; i <= m; ++i){
		int l, r, mx = 0, q = 0, sum;
		read(l), read(r);
		while(1){
			sum = getsum(mx + 1, q + 1, root[r], root[l - 1], 1, V);
			if(sum == 0){
//				cerr << sum << endl;
				write(q + 1);
				putchar('\n');
				break;
			}
			mx = q + 1;
			q += sum;
//			cerr << " q:" << q << " mx:" <<mx << " sum:" << sum << endl;
		}
	}
	return 0;
}
/*
若a[l, p - 1]已经添加，最大值为 mx, 且可以表示的数为[1, q]
若a[p] <= q + 1, 可以表示的数为[1, q + a[p]], 加入区间[a[p], a[p] + q] 
若a[p] > q + 1, q + 1为神秘数
最初p = l - 1, q = 0, mx = 0 
a[p]的范围为[mx + 1, q + 1], p为[p + 1, r]. p += 数量，q += sum.
若数量为0则ans = q + 1 
*/

结语

如果说线段树维护的是一维信息，可持久化线段树维护的就是二维可减信息，线段树部分维护第一维，“版本”部分维护第二维。例如部分扫描线、在线二维数点问题就可以通过可持久化线段树解决。
可持久化线段树维护静态平面信息（没有修改只有查询），动态维护需要用到树套树。
学会了可持久化线段树，其它可持久化数据结构就不难了。
希望你学得开心^^

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...