可持久化线段树

可持久化线段树（主席树）的原理与实现：历史版本查询与区间第 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 的可持久化数组。

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

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

struct PersistentArray {
    struct Node {
        int left = 0;
        int right = 0;
        int value = 0;
    };

    vector<Node> tree;

    explicit PersistentArray(int max_nodes) {
        tree.reserve(max_nodes);
        tree.push_back(Node{});
    }

    int clone(int p) {
        tree.push_back(tree[p]);
        return (int)tree.size() - 1;
    }

    int build(int l, int r, const vector<int>& a) {
        int p = clone(0);
        if (l == r) {
            tree[p].value = a[l];
            return p;
        }
        int mid = (l + r) >> 1;
        tree[p].left = build(l, mid, a);
        tree[p].right = build(mid + 1, r, a);
        return p;
    }

    int update(int p, int l, int r, int pos, int value) {
        int q = clone(p);
        if (l == r) {
            tree[q].value = value;
            return q;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            tree[q].left = update(tree[p].left, l, mid, pos, value);
        } else {
            tree[q].right = update(tree[p].right, mid + 1, r, pos, value);
        }
        return q;
    }

    int query(int p, int l, int r, int pos) const {
        if (l == r) return tree[p].value;
        int mid = (l + r) >> 1;
        if (pos <= mid) return query(tree[p].left, l, mid, pos);
        return query(tree[p].right, mid + 1, r, pos);
    }
};

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

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

    vector<int> 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) {
            int 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;
}

测试用例

输入：

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 模型一致。

参考