可持久化线段树
代码模板可持久化线段树(主席树)的原理与实现:历史版本查询与区间第 K 小。
一句话算法
可持久化线段树每次修改只复制从根到叶子的一条链,让新旧版本共享没有变化的节点。
问题模型
普通线段树修改后,旧状态会被覆盖。可持久化线段树解决的是“保留历史版本”的问题:
- 给定初始数组。
- 每次基于某个历史版本修改一个位置,生成新版本。
- 每次可以查询任意历史版本中的某个位置或区间信息。
以 luogu-P3919 为例,操作只有两类:
- 基于版本
v,把a[pos]改成value,生成新版本。 - 查询版本
v中a[pos]的值,同时复制出一个新版本。
核心直觉
一次单点修改只会影响线段树上从根到目标叶子的一条路径。路径之外的所有节点表示的区间完全没有变化,可以被新版本继续共享。
因此修改时:
- 复制旧根,得到新根。
- 沿着目标位置向下走,每经过一个节点就复制一个新节点。
- 没走到的另一个儿子直接指向旧版本的儿子。
- 到叶子后写入新值。
这样一次修改只新增
算法步骤
- 用普通线段树方式建立初始版本
root[0]。 update(old_root, pos, value):- 复制当前节点为新节点。
- 如果到达叶子,改值并返回新节点编号。
- 否则只递归修改包含
pos的那一边。 - 另一边直接复用旧节点。
query(root[v], pos):- 从版本
v的根节点出发。 - 按
pos所在区间向下走到叶子。 - 返回叶子保存的值。
- 从版本
算法证明
关键不变量: 对任意版本 v,从 root[v] 出发能访问到的节点,恰好组成这个版本对应的线段树。
- 初始版本:
build建出完整线段树,root[0]指向它,不变量成立。 - 修改路径: 单点修改只会改变包含
pos的区间节点;不包含pos的区间值不变,可以共享旧节点。 - 复制节点: 每次进入受影响节点时先复制,所以新版本的修改不会覆盖旧版本节点。
- 共享节点: 未被复制的子树没有任何内容变化,新旧版本指向同一棵子树不会改变查询结果。
- 查询正确: 查询只沿着版本根节点对应的树向下走,根据不变量,到达的叶子就是该版本中
pos的值。
复杂度分析
设数组长度为
- 建树时间复杂度:
。 - 单次修改时间复杂度:
,新增节点 。 - 单次查询时间复杂度:
。 - 总空间复杂度:
。
代码实现
下面模板对应 luogu-P3919 的可持久化数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 可持久化数组:每次修改只复制从根到该叶子的那一条链,
// 于是得到一个新版本,旧版本的所有节点原封不动,仍然可查。
const int maxn = 100000 + 5; // 数组长度上限
const int MAXNODE = 4000000 + 5; // 节点池大小:约 (n + m * log n)
int lc[MAXNODE]; // lc[p]:p 的左儿子下标,0 表示空
int rc[MAXNODE]; // rc[p]:p 的右儿子下标,0 表示空
ll val[MAXNODE]; // val[p]:叶子节点存的数组值
int tot = 0; // 已分配的节点数,0 号节点固定为空节点
// 复制节点 p(左右儿子与值原样照抄),返回新节点的下标
int clone(int p) {
++tot;
lc[tot] = lc[p];
rc[tot] = rc[p];
val[tot] = val[p];
return tot;
}
// 用 a[1..n] 建树,返回根节点下标
int seg_build(int l, int r, const ll *a) {
int p = clone(0);
if (l == r) {
val[p] = a[l];
return p;
}
int mid = (l + r) >> 1;
lc[p] = seg_build(l, mid, a);
rc[p] = seg_build(mid + 1, r, a);
return p;
}
// 在版本 p 上把位置 pos 改成 value,返回新版本的根下标
int update(int p, int l, int r, int pos, ll value) {
int q = clone(p); // 只复制这一个节点,没走到的子树继续和老版本共享
if (l == r) {
val[q] = value;
return q;
}
int mid = (l + r) >> 1;
if (pos <= mid) lc[q] = update(lc[p], l, mid, pos, value);
else rc[q] = update(rc[p], mid + 1, r, pos, value);
return q;
}
// 查询版本 p 中位置 pos 的值
ll query(int p, int l, int r, int pos) {
if (l == r) return val[p];
int mid = (l + r) >> 1;
if (pos <= mid) return query(lc[p], l, mid, pos);
return query(rc[p], mid + 1, r, pos);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
static ll a[maxn];
for (int i = 1; i <= n; i++) cin >> a[i];
// root[v]:第 v 个版本的根下标,版本 0 是初始版本
static int root[maxn];
root[0] = seg_build(1, n, a);
for (int i = 1; i <= m; i++) {
int version, op, pos;
cin >> version >> op >> pos;
if (op == 1) {
ll value;
cin >> value;
root[i] = update(root[version], 1, n, pos, value);
} else {
root[i] = root[version]; // 查询也占一个版本号,内容与来源版本相同
cout << query(root[version], 1, n, pos) << '\n';
}
}
return 0;
}
Python 版与 C++ 一一对应:全局列表 lc / rc / val 配 init(n, version_count)。update 返回新版本根(旧版本仍可查询),节点池用 append 动态增长,不需要 max_nodes 这类预分配参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# 可持久化数组:每次修改只复制从根到该叶子的那一条链,
# 于是得到一个新版本,旧版本的所有节点原封不动,仍然可查。
# 与 C++ 版一一对应:全局列表 lc / rc / val(下标即指针)+ 独立函数。
# 版本句柄就是根下标:root[v] 为第 v 个版本的根,0 号节点是空哨兵。
# 递归深度是线段树高度 O(log n),不会触及默认递归上限。
lc: list[int] = [0] # lc[p]:p 的左儿子下标,0 表示空
rc: list[int] = [0] # rc[p]:p 的右儿子下标,0 表示空
val: list[int] = [0] # val[p]:叶子节点存的数组值
tot: int = 0 # 已分配的节点数,0 号节点固定为空节点
base: list[int] = [] # 原始数组,建树时用 base[1..n]
root: list[int] = [] # root[v]:第 v 个版本的根下标
n: int = 0 # 数组长度
def init(size: int, version_count: int) -> None:
"""重置为长度 size、最多 version_count 个版本;换一组数据前必须先调用。"""
global lc, rc, val, tot, base, root, n
n = size
lc = [0]
rc = [0]
val = [0]
tot = 0
base = [0] * (n + 1)
root = [0] * (version_count + 1)
def clone(p: int) -> int:
"""复制节点 p(左右儿子与值原样照抄),返回新节点的下标。"""
global tot
tot += 1
lc.append(lc[p])
rc.append(rc[p])
val.append(val[p])
return tot
def seg_build(l: int, r: int) -> int:
"""用 base[1..n] 建树,返回根节点下标。"""
p = clone(0)
if l == r:
val[p] = base[l]
return p
mid = (l + r) >> 1
lc[p] = seg_build(l, mid)
rc[p] = seg_build(mid + 1, r)
return p
def update(p: int, l: int, r: int, pos: int, value: int) -> int:
"""在版本 p 上把位置 pos 改成 value,返回新版本的根下标。"""
q = clone(p) # 只复制这一个节点,没走到的子树继续和老版本共享
if l == r:
val[q] = value
return q
mid = (l + r) >> 1
if pos <= mid:
lc[q] = update(lc[p], l, mid, pos, value)
else:
rc[q] = update(rc[p], mid + 1, r, pos, value)
return q
def query(p: int, l: int, r: int, pos: int) -> int:
"""查询版本 p 中位置 pos 的值。"""
if l == r:
return val[p]
mid = (l + r) >> 1
if pos <= mid:
return query(lc[p], l, mid, pos)
return query(rc[p], mid + 1, r, pos)
测试用例
输入:
5 5
1 2 3 4 5
0 2 1
0 1 3 9
1 2 3
2 2 3
3 2 1
输出:
1
3
9
1
第一条查询读取初始版本的 a[1]。第二次修改基于初始版本把 a[3] 改成 9,后续查询可以同时看到旧版本的 3 和新版本的 9。
应用分类详解
可持久化线段树的本质是“用少量新增节点保存历史版本差异”。
一、可持久化数组
典型模式: 单点修改、查询历史版本单点值。 识别信号: 题面明确给出版本号,每次操作基于旧版本生成新版本。 核心建模: 线段树叶子保存数组值,每次修改复制根到叶子的一条链。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 历史数组 | luogu-P3919 | 每个版本保存一个根节点 |
二、区间第 k 小
典型模式: 静态数组,多次询问 [l,r] 中第 k 小。
识别信号: 没有修改,只有大量区间排名查询。
核心建模: 建立前缀版本权值线段树,root[r] - root[l-1] 表示区间频次。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 主席树模板 | luogu-P3834 | 两个版本相减得到区间内每个值的出现次数 |
| K-th Number | POJ 2104 | 离散化后在权值线段树上二分答案 |
三、历史区间信息
典型模式: 操作需要回到过去版本查询区间和、区间最值或其他可合并信息。 识别信号: 历史版本很多,但每次修改影响范围较小。 核心建模: 节点维护可合并信息,单点修改复制路径;区间修改通常要更谨慎,常见做法是标记永久化。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 历史区间和 | HDU 4348 To the moon | 持久化线段树配合标记永久化 |
经典例题
-
luogu-P3919 可持久化数组模板题。先掌握“复制一条链,共享其他节点”的基本写法。
-
luogu-P3834 主席树最经典应用。重点理解两个前缀版本相减表示区间频次。
-
POJ 2104 K-th Number 区间第 k 小模板题,和 P3834 模型一致。