可持久化线段树

代码模板

可持久化线段树(主席树)的原理与实现:历史版本查询与区间第 K 小。

一句话算法

可持久化线段树每次修改只复制从根到叶子的一条链,让新旧版本共享没有变化的节点。

问题模型

普通线段树修改后,旧状态会被覆盖。可持久化线段树解决的是“保留历史版本”的问题:

  • 给定初始数组。
  • 每次基于某个历史版本修改一个位置,生成新版本。
  • 每次可以查询任意历史版本中的某个位置或区间信息。

以 luogu-P3919 为例,操作只有两类:

  1. 基于版本 v,把 a[pos] 改成 value,生成新版本。
  2. 查询版本 v 中 a[pos] 的值,同时复制出一个新版本。

核心直觉

一次单点修改只会影响线段树上从根到目标叶子的一条路径。路径之外的所有节点表示的区间完全没有变化,可以被新版本继续共享。

因此修改时:

  1. 复制旧根,得到新根。
  2. 沿着目标位置向下走,每经过一个节点就复制一个新节点。
  3. 没走到的另一个儿子直接指向旧版本的儿子。
  4. 到叶子后写入新值。

这样一次修改只新增 O(log⁡n)O(\log n) 个节点。

算法步骤

  1. 用普通线段树方式建立初始版本 root[0]。
  2. update(old_root, pos, value):
    • 复制当前节点为新节点。
    • 如果到达叶子,改值并返回新节点编号。
    • 否则只递归修改包含 pos 的那一边。
    • 另一边直接复用旧节点。
  3. query(root[v], pos):
    • 从版本 v 的根节点出发。
    • 按 pos 所在区间向下走到叶子。
    • 返回叶子保存的值。

算法证明

关键不变量: 对任意版本 v,从 root[v] 出发能访问到的节点,恰好组成这个版本对应的线段树。

  1. 初始版本: build 建出完整线段树,root[0] 指向它,不变量成立。
  2. 修改路径: 单点修改只会改变包含 pos 的区间节点;不包含 pos 的区间值不变,可以共享旧节点。
  3. 复制节点: 每次进入受影响节点时先复制,所以新版本的修改不会覆盖旧版本节点。
  4. 共享节点: 未被复制的子树没有任何内容变化,新旧版本指向同一棵子树不会改变查询结果。
  5. 查询正确: 查询只沿着版本根节点对应的树向下走,根据不变量,到达的叶子就是该版本中 pos 的值。

复杂度分析

设数组长度为 nn,操作次数为 mm。

  • 建树时间复杂度:O(n)O(n)。
  • 单次修改时间复杂度:O(log⁡n)O(\log n),新增节点 O(log⁡n)O(\log n)。
  • 单次查询时间复杂度:O(log⁡n)O(\log n)。
  • 总空间复杂度:O(n+mlog⁡n)O(n+m\log n)。

代码实现

下面模板对应 luogu-P3919 的可持久化数组。

C++
cpp
        
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

Python 版与 C++ 一一对应:全局列表 lc / rc / val 配 init(n, version_count)。update 返回新版本根(旧版本仍可查询),节点池用 append 动态增长,不需要 max_nodes 这类预分配参数。

python
        
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 持久化线段树配合标记永久化

经典例题

  1. luogu-P3919 可持久化数组模板题。先掌握“复制一条链,共享其他节点”的基本写法。

  2. luogu-P3834 主席树最经典应用。重点理解两个前缀版本相减表示区间频次。

  3. POJ 2104 K-th Number 区间第 k 小模板题,和 P3834 模型一致。

参考