进阶数据结构：主席树（可持久化线段树）

什么叫“可持久化”？

在算法竞赛中，“可持久化”通常指一种数据结构技术，它允许我们在修改数据结构后，仍然能访问到修改前（即历史版本）的数据。

主席树的核心思想

主席树，又称可持久化（权值）线段树，是可持久化思想的经典应用。它通过巧妙地复用节点，实现了在保持历史版本的同时，高效地创建新版本。

当我们对线段树进行单点修改时，从根节点到目标叶子节点的路径上，最多只有 log(N) 个节点会发生改变。可持久化的思想就是：只创建这 log(N) 个新的节点，而路径上其他未改变的节点，则直接链接到旧版本的对应节点上。

每次修改都会产生一个新的树根（Root），代表一个新的版本。通过保存这些不同的树根，我们就能访问任意历史版本的线段树。

结构示意

假设我们修改了版本 i 的某个值，得到版本 j：

• 版本 i 的根是 root[i]。
• 版本 j 的根是 root[j]。
• root[j] 会复制 root[i] 的信息，并根据修改路径创建新的节点。如果修改在左子树，那么 root[j] 的右儿子就直接指向 root[i] 的右儿子，而左儿子则指向一个新创建的节点。这个过程递归地进行下去。

由于每次修改只增加 log(N) 个新节点，所以 M 次修改后的总空间复杂度是 O(N + M log N)，非常高效。

经典应用：静态区间第 K 小

主席树最经典的应用就是解决静态区间的第 K 小问题。

1. 离散化: 将所有数值进行离散化。
2. 建树:
   • 我们对原始数组的 前缀 建立权值线段树。
   • 第 i 个版本的线段树 (root[i]) 存储的是原数组 a[1...i] 中各个数值出现的次数。
   • 版本 i 的线段树是通过在版本 i-1 的基础上，对 a[i] 的值进行一次单点更新得到的。
3. 查询 [L, R] 区间的第 K 小:
   • 利用线段树的可减性，我们可以通过 root[R] 和 root[L-1] 这两个版本的信息，来得到区间 [L, R] 的权值线段树。
   • 具体来说，root[R] 的某个节点值减去 root[L-1] 的对应节点值，就等于 a[L...R] 中落在这个值域区间的数的个数。
   • 我们可以在这两棵树上同步进行类似权值线段树��查询第 K 小的操作。如果左子树的数的个数 count 大于等于 k，我们就往左走；否则，我们就往右走，并查询第 k - count 小。

主席树是处理可持久化问题和区间问题的强大工具，是数据结构进阶路上必须掌握的一环。