我的算法书 - 可持久化线段树

一句话算法

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

问题模型

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

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

以 luogu-P3919 为例，操作只有两类：

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

核心直觉

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

因此修改时：

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

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

算法步骤

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

算法证明

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

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

复杂度分析

设数组长度为 $n$ ，操作次数为 $m$ 。

建树时间复杂度： $O(n)$ 。
单次修改时间复杂度： $O(\log n)$ ，新增节点 $O(\log n)$ 。
单次查询时间复杂度： $O(\log 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
87
88
89
90
91
92
93
94
95
96
97
98

        #include <bits/stdc++.h>
using namespace std;

// 可持久化数组：每次修改产生一个新版本，旧版本仍然可查询
struct PersistentArray {
    // 线段树节点：left/right 为左右孩子下标，value 为单点值
    using T = long long;
    struct Node {
        int left = 0;   // 左孩子下标，0 表示空
        int right = 0;  // 右孩子下标，0 表示空
        T value = 0;    // 叶子节点存数组值
    };

    vector<Node> tree;  // 动态节点池，节点下标即指针

    explicit PersistentArray(int max_nodes) {
        tree.reserve(max_nodes);
        tree.push_back(Node{});  // 0 号节点为空节点
    }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    // 复制节点 p 并返回新节点下标
    int clone(int p) {
        tree.push_back(tree[p]);
        return (int)tree.size() - 1;
    }

    // 用数组 a 建树，返回根节点下标
    int build(int l, int r, const vector<T> &a) {
        int p = clone(0);
        if (l == r) {
            tree[p].value = a[l];
            return p;
        }
        int m = mid(l, r);
        tree[p].left = build(l, m, a);
        tree[p].right = build(m + 1, r, a);
        return p;
    }

    // 基于版本 p 修改位置 pos 为 value，产生新版本，返回新根下标
    int update(int p, int l, int r, int pos, T value) {
        int q = clone(p);
        if (l == r) {
            tree[q].value = value;
            return q;
        }
        int m = mid(l, r);
        if (pos <= m) {
            tree[q].left = update(tree[p].left, l, m, pos, value);
        } else {
            tree[q].right = update(tree[p].right, m + 1, r, pos, value);
        }
        return q;
    }

    // 查询版本 p 中位置 pos 的值
    T query(int p, int l, int r, int pos) const {
        if (l == r) return tree[p].value;
        int m = mid(l, r);
        if (pos <= m) return query(tree[p].left, l, m, pos);
        return query(tree[p].right, m + 1, r, pos);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int max_nodes = n + m * 20 + 5;
    PersistentArray seg(max_nodes);

    vector<int> root(m + 1);
    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) {
            long long value;
            cin >> value;
            root[i] = seg.update(root[version], 1, n, pos, value);
        } else {
            root[i] = root[version];
            cout << seg.query(root[version], 1, n, pos) << '\n';
        }
    }

    return 0;
}

Python

max_nodes 参数仅为接口对齐保留（Python 列表动态增长）；update 返回新版本根，旧版本仍可查询。

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

        # 可持久化数组：每次 update 只复制一条到根的路径，产生新版本，旧版本仍可查询。
# 节点用下标池存储，0 号为空节点；根下标即版本句柄（对应 C++ 的 root[版本]）。
# build / update / query 递归深度均为线段树高度 O(log n)，不会触及默认递归上限。
# C++ 用 long long 存值，Python int 任意精度，无溢出问题。


class Node:
    """线段树节点：left/right 为孩子下标（0 表示空），value 为单点值。"""

    __slots__ = ("left", "right", "value")

    def __init__(self) -> None:
        self.left = 0
        self.right = 0
        self.value = 0


class PersistentArray:
    def __init__(self, max_nodes: int) -> None:
        # C++ 的 max_nodes 用于 reserve 预分配；Python list 动态扩容，该参数仅为
        # 保持接口一致而保留，不参与逻辑（传任意非负整数都不影响结果）。
        self.tree: list[Node] = [Node()]  # 0 号节点为空节点

    @staticmethod
    def mid(l: int, r: int) -> int:
        return (l + r) >> 1

    def clone(self, p: int) -> int:
        """复制节点 p 并返回新节点下标（浅拷贝 l/r/value，与 C++ 逐字段复制一致）。"""
        src = self.tree[p]
        node = Node()
        node.left, node.right, node.value = src.left, src.right, src.value
        self.tree.append(node)
        return len(self.tree) - 1

    def build(self, l: int, r: int, a: list[int]) -> int:
        """用 1 下标数组 a 的 [l, r] 建树，返回根下标。"""
        p = self.clone(0)
        if l == r:
            self.tree[p].value = a[l]
            return p
        m = self.mid(l, r)
        self.tree[p].left = self.build(l, m, a)
        self.tree[p].right = self.build(m + 1, r, a)
        return p

    def update(self, p: int, l: int, r: int, pos: int, value: int) -> int:
        """基于版本 p 把位置 pos 改成 value，返回新版本根下标（不改动原版本）。"""
        q = self.clone(p)
        if l == r:
            self.tree[q].value = value
            return q
        m = self.mid(l, r)
        if pos <= m:
            self.tree[q].left = self.update(self.tree[p].left, l, m, pos, value)
        else:
            self.tree[q].right = self.update(self.tree[p].right, m + 1, r, pos, value)
        return q

    def query(self, p: int, l: int, r: int, pos: int) -> int:
        """查询版本 p 中位置 pos 的值。"""
        if l == r:
            return self.tree[p].value
        m = self.mid(l, r)
        if pos <= m:
            return self.query(self.tree[p].left, l, m, pos)
        return self.query(self.tree[p].right, m + 1, r, pos)

测试用例

输入：

输出：

第一条查询读取初始版本的 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 模型一致。

参考

线段树，从入门到入坑 - AcWing