CC++ & Algorithm

可持久化线段树（主席树）

极难2
语言版本：通用
概述：给每个历史版本都保存一颗线段树，因为只修改了路径上的log n个节点，所以能共享大部分节点。

可持久化线段树（主席树）：给数据拍“快照”，只存差异不存全部

你有没有这样的经历：在游戏里打怪升级，每天保存一次进度，第二天想看看第一天是什么状态？或者记录零花钱，每次花完钱记一笔，后来想查查上个星期的余额？如果每次修改都重新抄写一整本账本，太浪费纸了！可持久化线段树（也叫主席树）就是专门解决这个问题的——它能把每次修改后的状态都保留下来，但只记录“改动了哪几处”，其他没变的部分大家共用，省空间又高效。

生活中的存档与复刻

想象你有一本练习册，上面按顺序写了100个数字。第一天你改了第5个数字，第二天又改了第20个……一个月后，你想知道“第3天的时候，第10到第15个数字的和是多少？”
普通做法：每天抄一本新练习册，一个月后就有30本，每本100个数字，太浪费。
聪明做法：只记录每天改动的那几个数字，其他没变的页面直接从旧本子上“借”过来看。这样每天只需要多写几个数字，就能随时回到任何一天。

可持久化线段树就是这种“聪明做法”在计算机里的实现。它把线段树（一种按区间存储数据的二叉树）的每个版本都保存下来，但每次修改只新建从根到叶子的那条路径上的节点（大约 log₂n 个），其它分支直接指向旧版本。这样，我们就能用有限的空间，查询任意历史版本的任意区间信息。

核心思想：只存差异，复用节点

1. 普通线段树的缺点

普通线段树每个节点存一个区间（比如[1,4]）的和。修改一个位置时，会从根走到叶子，沿途更新所有节点的值。但无法保留旧版本，改完就没了。

2. 可持久化的做法

  • 每个版本都有一个根节点指针。我们用一个数组 root[] 记录每个版本的根。
  • 当修改某个位置时，从旧版本的根出发，复制一份新节点，然后沿着要修改的路径，每遇到一个节点就新建一个副本（复制旧节点的左右儿子指针和值），然后递归下去。
  • 没被修改的分支（比如左子树没动），新节点的左儿子直接指向旧版本的那个左儿子节点，共享。
  • 结果：只有 O(log n) 个节点是新创建的，其他节点仍然被旧版本使用。

3. 一个简单例子（3个数字的线段树）

假设初始数组 [a1, a2, a3]，对应的线段树（叶子节点存数字，父节点存区间和）：

        [1,3]  sum=a1+a2+a3
       /        \
   [1,2]        [3] (叶子)
  /     \
[1]    [2] (叶子)

现在把位置 2 的数字改成新值。新建节点如下（用 * 表示新节点）：

        [1,3]*          ← 新根
       /        \
   [1,2]        [3]  ← 右子树没动，共享旧节点
  /     \
[1]    [2]*           ← 叶子新建

左子树中[1]节点没动，共享。所以只新建了根、右子节点（[1,2]）、叶子[2]，共3个节点。

图解可持久化过程（更详细）

下面是四个节点的例子（数组[1..4]）。初始版本0的结构：

版本0根: 节点A
        A([1,4]和=10)
       /        \
    B([1,2])   C([3,4])
   /    \      /    \
 D([1]) E([2])F([3]) G([4])

现在修改位置3的值为新值（比如从3变成100），创建版本1。流程：

  1. 新建节点A'，复制A的信息（左= B，右= C）。
  2. 因为要往右走，新建节点C'，复制C的信息（左= F，右= G）。
  3. 再往左走（位置3在[3,4]的左半），新建节点F'，复制F，把值改成100。
  4. 回溯更新A'的和 = B的和 + C'的和，C'的和 = F'的值 + G的值。

最终版本1的树：

版本1根: A'
        A'([1,4]和=107)
       /        \
    B([1,2])   C'([3,4]和=103)  ← 新建
   /    \      /    \
 D([1]) E([2])F'([3]=100) G([4])

注意：B、D、E、G还是版本0的节点，完全共享。新节点只有A', C', F'三个。

如何查询历史版本

查询时，用对应版本的根，像普通线段树一样递归即可。例如查询版本1中区间[2,3]的和：从A'开始，往左走到B（查[2,2]），往右走到C'（查[3,3]），得到结果 E的和 + F'的值。

所有版本共享底层节点，所以查询速度也是O(log n)。

空间复杂度与节点池大小

每次修改新增 O(log n) 个节点，假设有 m 次修改，总节点数约为 n + m * log n（初始树 n 个节点）。通常我们预留 n * (log2(n)+1) * 4 的空间，比如 n=100000，log₂n≈17，可开 100000 * 20 * 4 = 8000000 个节点。实践中可以稍微大一点。

注意：如果用数组存节点，一定要算好最大节点数，否则数组越界导致段错误。

常见错误（新手容易踩的坑）

  1. 忘记复制旧节点信息
    update 函数里，新建节点后要先复制 tree[p] = tree[pre]（或手动复制 l, r, sum），否则新节点左右儿子未定义，会乱指。

  2. 版本号管理混乱
    初始版本0用 root[0] 记录，每次修改后 cur++，把新根存到 root[cur]。查询时一定要用 root[v]，v 是版本号，不是节点编号。

  3. 递归时传错边界
    update 和 query 里递归时要传对 l, r 区间，尤其是分左右时注意 mid 的归属。

  4. 节点池大小不够
    假设 n=100000，q=100000，最多新增节点数 ≈ 1e5 * 17 ≈ 1.7e6，加上初始节点约1e5，总节点约1.8e6。如果数组只开了 MAXN*LOG 而没乘4，可能不够。

  5. 查询时不使用对应版本的根
    要查版本 v，必须用 root[v] 作为根节点，不要误用其他版本。

完整可运行代码（C++ 带详细注释）

下面代码实现一个可持久化线段树，支持单点修改和区间和查询。输入格式：

  • 第一行 n, q
  • 第二行 n 个初始数字
  • 接下来 q 行，每行一个操作：
    • 1 v x y：基于版本 v，将位置 x 的值改为 y
    • 2 v x y：查询版本 v 中区间 [x,y] 的和
#include <iostream>
using namespace std;

const int MAXN = 100005;      // 数组最大长度
const int LOG = 20;           // log2(MAXN) ≈ 17，多留一点
const int MAXNODES = MAXN * LOG * 4; // 预留节点池大小

struct Node {
    int l, r;   // 左右儿子在 tree 数组中的下标
    int sum;    // 区间和
} tree[MAXNODES];   // 节点池

int root[MAXN]; // root[version] = 该版本根节点的下标
int cnt = 0;    // 当前已用的节点数（下标从1开始）
int n, q;
int arr[MAXN];  // 初始数组，下标从1开始

// 建立版本0的线段树，返回根节点下标
int build(int l, int r) {
    int p = ++cnt;               // 分配一个新节点
    if (l == r) {
        tree[p].sum = arr[l];    // 叶子存数字
        tree[p].l = tree[p].r = 0;
        return p;
    }
    int mid = (l + r) / 2;
    tree[p].l = build(l, mid);   // 递归建左子树
    tree[p].r = build(mid + 1, r); // 递归建右子树
    tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum;
    return p;
}

// 基于旧版本 pre，将位置 pos 的值改为 val，返回新版本的根
int update(int pre, int l, int r, int pos, int val) {
    int p = ++cnt;               // 新建节点
    tree[p] = tree[pre];         // 复制旧节点的左右儿子和sum
    if (l == r) {
        tree[p].sum = val;       // 叶子修改值
        return p;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) {
        // 修改左子树：新的左儿子由旧左儿子递归修改得到
        tree[p].l = update(tree[pre].l, l, mid, pos, val);
    } else {
        // 修改右子树
        tree[p].r = update(tree[pre].r, mid + 1, r, pos, val);
    }
    // 更新当前节点的和
    tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum;
    return p;
}

// 查询版本 ver 中区间 [ql, qr] 的和
int query(int ver, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[ver].sum;    // 完全包含，直接返回
    }
    int mid = (l + r) / 2;
    int res = 0;
    if (ql <= mid) {
        res += query(tree[ver].l, l, mid, ql, qr);
    }
    if (qr > mid) {
        res += query(tree[ver].r, mid + 1, r, ql, qr);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    root[0] = build(1, n);      // 版本0（初始版本）
    int cur = 0;                // 当前最新版本号

    while (q--) {
        int op, v, x, y;
        cin >> op;
        if (op == 1) {
            // 基于版本 v，修改位置 x 为 y
            cin >> v >> x >> y;
            cur++;
            root[cur] = update(root[v], 1, n, x, y);
        } else {
            // 查询版本 v 的区间 [x, y] 和
            cin >> v >> x >> y;
            cout << query(root[v], 1, n, x, y) << '\n';
        }
    }
    return 0;
}

输入输出示例

输入：

5 4
1 2 3 4 5          # 初始数组 [1,2,3,4,5]
1 0 3 10           # 基于版本0，将位置3改为10 -> 版本1
2 1 2 4            # 查询版本1中[2,4]的和 -> 2+10+4=16
1 1 5 100          # 基于版本1，将位置5改为100 -> 版本2
2 2 3 5            # 查询版本2中[3,5]的和 -> 10+4+100=114

输出：

16
114

Python 完整代码实现（带详细注释）

class Node:
    """线段树节点"""
    def __init__(self, l=0, r=0, sum=0):
        self.l = l      # 左儿子在list中的索引
        self.r = r      # 右儿子索引
        self.sum = sum  # 区间和

class PersistentSegTree:
    def __init__(self, n, arr):
        self.n = n
        self.tree = [Node()]       # 预留索引0，实际节点从1开始
        self.root = [0]            # root[版本号] = 根节点索引
        self.cnt = 0               # 当前节点数
        self.arr = arr             # arr[1..n]
        # 建立版本0
        self.root.append(self.build(1, n))

    def new_node(self, l=0, r=0, sum=0):
        """创建新节点，返回索引"""
        self.tree.append(Node(l, r, sum))
        self.cnt += 1
        return self.cnt

    def build(self, l, r):
        """建树，返回根索引"""
        p = self.new_node()
        if l == r:
            self.tree[p].sum = self.arr[l]
            return p
        mid = (l + r) // 2
        self.tree[p].l = self.build(l, mid)
        self.tree[p].r = self.build(mid + 1, r)
        self.tree[p].sum = self.tree[self.tree[p].l].sum + self.tree[self.tree[p].r].sum
        return p

    def update(self, pre, l, r, pos, val):
        """基于旧版本根pre，修改pos为val，返回新根"""
        p = self.new_node()
        # 复制旧节点信息
        self.tree[p].l = self.tree[pre].l
        self.tree[p].r = self.tree[pre].r
        self.tree[p].sum = self.tree[pre].sum
        if l == r:
            self.tree[p].sum = val
            return p
        mid = (l + r) // 2
        if pos <= mid:
            self.tree[p].l = self.update(self.tree[pre].l, l, mid, pos, val)
        else:
            self.tree[p].r = self.update(self.tree[pre].r, mid + 1, r, pos, val)
        self.tree[p].sum = self.tree[self.tree[p].l].sum + self.tree[self.tree[p].r].sum
        return p

    def query(self, ver, l, r, ql, qr):
        """查询版本 ver 中区间 [ql,qr] 的和"""
        if ql <= l and r <= qr:
            return self.tree[ver].sum
        mid = (l + r) // 2
        res = 0
        if ql <= mid:
            res += self.query(self.tree[ver].l, l, mid, ql, qr)
        if qr > mid:
            res += self.query(self.tree[ver].r, mid + 1, r, ql, qr)
        return res

def main():
    n, q = map(int, input().split())
    arr = [0] + list(map(int, input().split()))   # 下标从1开始
    seg = PersistentSegTree(n, arr)
    cur = 0
    for _ in range(q):
        op, *rest = map(int, input().split())
        if op == 1:
            v, x, y = rest
            cur += 1
            # 新版本根追加到root列表
            seg.root.append(seg.update(seg.root[v], 1, n, x, y))
        else:
            v, x, y = rest
            print(seg.query(seg.root[v], 1, n, x, y))

if __name__ == "__main__":
    main()

相关指引

学会了主席树，你就可以解决很多“历史版本查询”的问题了：

  • 静态区间第 k 小（大）：主席树的经典应用。把数组每个前缀建成一棵权值线段树，利用可持久化，在 O(log n) 时间内查询任意区间内第 k 小的数。很多竞赛题（如“K-th Number”）就是用它。
  • 可持久化数组：这就是本文实现的功能，支持单点修改和查询任意历史版本的值。
  • 可持久化并查集：在主席树上维护并查集，支持回退到历史版本。
  • 树上路径权值第 k 小：结合树上差分和主席树，查询树上两点间路径的权值第 k 小。

另外，主席树也常与离散化配合使用，当值域很大时，先排序去重，然后建树在离散后的下标上。

总之，主席树就像给数据拍了一串“快照”，每次只保存差异，极大节省空间，又能随时回到任意时刻。下次你写作业时，是不是也希望有这样的“存档”功能呢？

例题精讲

1单选题

可持久化线段树（主席树）实现可持久化的核心思想是什么？

A每次修改时复制整棵树
B只复制被修改节点到根节点路径上的节点
C使用延迟标记进行可持久化
D通过平衡树实现可持久化
2单选题

主席树最经典的应用场景是以下哪个？

A动态区间最大值查询
B静态区间第k小查询
C区间众数查询
D区间异或和查询
3判断题

主席树的空间复杂度通常为O(n log n)，其中n为原始数组长度。

4填空题
下面是主席树插入节点的递归函数，请填空：
int update(int pre, int l, int r, int pos) {
    int cur = ++tot;
    sum[cur] = sum[pre] + 1;
    if (l == r) return cur;
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        ___;
        rson[cur] = rson[pre];
    } else {
        lson[cur] = lson[pre];
        ___;
    }
    return cur;
}
5填空题
下面是主席树查询区间第k小的递归函数，请填空：
int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int x = ___;
    if (k <= x) {
        return query(lson[u], lson[v], l, mid, k);
    } else {
        return query(rson[u], rson[v], mid+1, r, ___);
    }
}