第 98 课 - 可持久化数据结构 (Persistent Data Structures)

学习目标

完成本课学习后，你将能够：

理解可持久化的概念：明白什么是可持久化数据结构，以及它在算法竞赛中的核心应用场景（保留历史版本）。
掌握路径复制的原理：理解通过“共享”和“复制”部分节点来实现多版本管理的核心技术思想。
学习主席树（Persistent Segment Tree）的实现：掌握可持久化线段树的构建、更新和查询过程。
分析时空复杂度：了解可持久化数据结构相较于普通数据结构在空间与时间上的权衡。
应用可持久化思想：能够将“保留历史版本”的思路迁移到其他基础数据结构（如线段树、平衡树）上。

核心概念

为什么需要可持久化？ 想象你在玩一个游戏，你可以随时读取过去任意一个时间点的存档。一个普通的数组在每次修改后，旧版本的数据就丢失了。可持久化数据结构，就是数据结构领域的“存档系统”。它允许我们保存数据结构的所有历史版本，并且可以高效地查询任意历史版本的信息，同时新版本的创建开销相对较小。

关键思想：路径复制（Path Copying） 这是实现可持久化最核心、最直观的技巧。其思路源于树状结构（如线段树、二叉搜索树）。当我们需要基于一个旧版本（Version t）创建一个新版本（Version t+1）并只修改其中一个元素时，我们不需要复制整棵树。

我们只需要：

复制从根节点到被修改叶子节点路径上的所有节点。
对于路径上的节点，让其指针指向新复制的子节点。
对于不在路径上的节点，直接让新节点的指针指向旧版本的对应节点（即“共享”）。

这样一来，新版本和旧版本共享了大部分未修改的子树，极大地节省了空间。每个版本的创建，都对应着一次“路径复制”。

以可持久化线段树（主席树）为例 主席树是可持久化思想应用最广泛的例子之一。它通常用于解决静态区间第k小值等涉及“历史版本”的问题。假设我们有一个序列 a，要建立一棵权值线段树来维护每个数出现的次数。我们不是建立一棵，而是建立 n 棵（每个前缀 a[1..i] 对应一棵）。第 i 棵线段树表示 a[1..i] 中各个数值的出现情况。

为了高效构建，我们利用了路径复制：从第 i-1 棵树，通过插入 a[i]，得到第 i 棵树。插入过程只影响 logN 个节点（路径复制），所以构建总复杂度是 O(NlogN)，空间也是 O(NlogN)。

查询区间 [l, r] 的信息时，我们只需要用第 r 棵树的状态减去第 l-1 棵树的状态，就得到了区间 [l, r] 的信息。

代码示例

下面是一个完整的、可运行的 可持久化权值线段树（主席树） 的 C++ 实现，用于解决 静态区间第k小值 问题。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005; // 假设序列最大长度
const int MAXM = 10005;  // 假设值域最大范围

struct ChairmanTree {
    int l, r; // 节点表示的值域区间
    int sum;  // 该区间内数字的出现次数之和
} tree[MAXN * 20]; // 预估空间，约为 N * logN

int cnt; // 节点计数器，分配新节点ID

// 新建一个节点，复制一个节点的内容
int newNode(int &p) {
    tree[++cnt] = tree[p]; // 复制旧节点的全部信息
    return cnt;            // 返回新节点的ID
}

// 构建初始的空树（值域[1, m]）
int build(int l, int r) {
    int root = ++cnt;
    tree[root].sum = 0;
    if (l == r) {
        // 叶子节点，初始和为0
        return root;
    }
    int mid = (l + r) >> 1;
    tree[root].l = build(l, mid);
    tree[root].r = build(mid + 1, r);
    return root;
}

// 在旧版本p的基础上，在位置pos增加一个数（出现次数+1）
int update(int p, int l, int r, int pos) {
    int root = newNode(p); // 复制路径上的节点
    tree[root].sum++;      // 当前区间的总数+1
    if (l == r) {
        // 到达叶子节点，更新完成
        return root;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        // 在左子树中更新，并指向新的左子树根节点
        tree[root].l = update(tree[p].l, l, mid, pos);
    } else {
        // 在右子树中更新，并指向新的右子树根节点
        tree[root].r = update(tree[p].r, mid + 1, r, pos);
    }
    return root;
}

// 查询区间[ql, qr]中，值域在[l, r]内的数字个数（差分思想）
int query(int ql, int qr, int l, int r, int k) {
    if (l == r) {
        // 找到了第k小的值所在的叶子节点
        return l;
    }
    int mid = (l + r) >> 1;
    // 左子树中数字的个数 = 第qr棵树的左子树和 - 第ql-1棵树的左子树和
    int leftCount = tree[tree[qr].l].sum - tree[tree[ql].l].sum;
    if (k <= leftCount) {
        // 第k小在左子树中，递归查询左子树
        return query(tree[ql].l, tree[qr].l, l, mid, k);
    } else {
        // 第k小在右子树中，在右子树中查询第(k - leftCount)小的
        return query(tree[ql].r, tree[qr].r, mid + 1, r, k - leftCount);
    }
}

int root[MAXN]; // root[i] 存储前缀 a[1..i] 对应的线段树根节点
int a[MAXN];    // 原始序列
int sorted[MAXN]; // 用于离散化的排序数组

int main() {
    int n, m; // n: 序列长度， m: 查询数量
    cin >> n >> m;

    // 1. 读入数据并离散化
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sorted[i] = a[i];
    }
    sort(sorted + 1, sorted + 1 + n);
    // 去重
    int unique_cnt = unique(sorted + 1, sorted + 1 + n) - sorted - 1;

    // 2. 构建空树（值域1到unique_cnt）
    root[0] = build(1, unique_cnt);

    // 3. 构建n个版本的主席树
    for (int i = 1; i <= n; i++) {
        // 将a[i]映射到离散化后的排名（值域[1, unique_cnt]中的位置）
        int pos = lower_bound(sorted + 1, sorted + 1 + unique_cnt, a[i]) - sorted;
        // 基于前一个版本root[i-1]，插入a[i]得到新版本root[i]
        root[i] = update(root[i-1], 1, unique_cnt, pos);
    }

    // 4. 处理查询
    for (int i = 1; i <= m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        // 查询区间[l, r]的第k小值在离散化后的位置（排名）
        int rank = query(root[l-1], root[r], 1, unique_cnt, k);
        // 将排名映射回原值
        cout << sorted[rank] << endl;
    }

    return 0;
}

代码运行示例输入：

代码运行示例输出：

2
3
1

解释：

序列 [3,2,1,4,5]
查询1：子序列 [3,2,1] 的第2小值是 2。
查询2：子序列 [2,1,4,5] 的第3小值是 4。
查询3：整个序列 [3,2,1,4,5] 的第1小值是 1。

实践练习

练习 1：查询历史区间最小值 (简单)

假设我们有一个初始为空、值域为 1~10 的可持久化权值线段树（使用上面的框架）。我们依次进行以下操作：insert(5), insert(3), insert(7), insert(1)。请修改 query 函数，使其能够查询任意历史版本中，值在某个范围 [L, R] 内的数字出现的总次数。给出修改后的 query 函数核心代码，并写出当查询“在插入 3 之后（版本2），值在 [2,5] 之间的数出现的总次数”的预期输出。

练习 2：静态区间第k小值 (中等)

使用本课提供的完整 ChairmanTree 代码，解决以下问题：输入：一个长度为 n 的序列 a，和 m 次查询，每次查询给定 l, r, k，求子序列 a[l..r] 中第 k 小的值。要求：自行构造一组输入数据（例如 n=6, a=[5,3,2,8,1,4]），并手动模拟或运行程序验证你的代码能正确输出所有查询结果。

练习 3：扩展应用 (困难)

在上面的主席树中，每个节点维护的是一个数字的出现次数。思考一下，如果我们希望支持 “查询区间[l, r]中，值在[a, b]范围内的数字之和” ，需要对现有的数据结构进行哪些修改？请描述需要修改的结构体定义、update 函数以及 query 函数的关键变化。不需要写出完整代码，但请给出清晰的思路说明。

常见错误

忘记路径复制：在 update 函数中，误以为直接修改旧节点 p 的 sum 或孩子指针即可。必须先调用 newNode(p) 复制出一个新节点，否则会破坏历史版本。
空间计算不足：tree 数组的大小开得太小，导致运行时访问越界。20 * MAXN 是一个常用的经验值，但更安全的做法是使用 vector 并在 newNode 中动态分配。
版本索引混乱：root 数组的下标与序列下标的关系要理清。root[i] 通常表示前 i 个元素的状态，因此查询 [l, r] 时，要用 root[r] 减去 root[l-1]。
值域处理错误：在进行权值线段树操作前，忘记对序列进行离散化，或者离散化后，update 和 query 中传入的 pos 参数计算错误（应映射到排序去重后的排名，而非原值）。
递归边界条件：在 query 函数中，递归终止条件是 l == r，此时返回的 l 是离散化后的值，还需要映射回原值。不要忘记这一步。

小结

核心思想：可持久化数据结构的核心是 路径复制。只在修改路径上创建新节点，其他部分与旧版本共享，从而在几乎不增加时间复杂度（O(logN) per update）的前提下，高效地保存了所有历史版本。
主席树（可持久化线段树）：是这一思想的经典实现。通过为序列的每个前缀建立权值线段树的版本，并利用差分思想，可以高效解决 静态区间第k小值 等问题。
空间换时间：可持久化通常会带来 O(NlogN) 级别的空间消耗，这是它能管理多个版本的代价。在竞赛中，需要根据题目给定的数据范围合理评估空间。
应用场景：凡是需要“询问某个历史时刻的状态”、“支持撤销操作”或者“比较不同版本数据结构”的问题，都可以考虑使用可持久化数据结构。常见的可持久化结构包括线段树、平衡树（如Treap）、并查集等。

练习编辑器

rust