核心逻辑与数学原理
可持久化线段树（Persistent Segment Tree），在竞赛界常被称为主席树。其核心解决的问题是：在对数级时间与空间复杂度内，回溯并查询线段树的历史版本，或者解决不带修改的区间静态第 $K$ 大问题。
1. 函数式状态与路径复制（Path Copying）
如果我们为每一次修改都暴力复制整棵线段树，空间复杂度将达到 $O(M \cdot N)$。可持久化线段树的核心数学逻辑是：相邻两个版本（例如版本 $t-1$ 与版本 $t$）之间，由于单点修改只改变了树中的一条链，因此两个版本之间有且仅有 $\lceil \log_2 N \rceil$ 个节点发生了状态改变，其余的大量非修改子树完全可以共享。
- 操作手法：当在版本 $t$ 修改某个叶子节点时，我们不直接在原树上覆盖，而是新建一个根节点 $Root[t]$。沿着修改路径向下递归，每到达一个节点，就复制一个一模一样的新节点。
- 指针重定向：新节点的未修改分支直接指向旧版本树上的对应子节点，修改分支则指向新建立的下层新节点。
- 空间复杂度证明：每次单点修改仅新建 $\lceil \log_2 N \rceil$ 个节点。做 $M$ 次修改，总空间复杂度硬收敛在 $O(N + M \log N)$ 级别。
2. 区间第 $K$ 大的前缀和差分原理
可持久化权值线段树通过前缀和的思想，硬核破局“区间第 $K$ 大”这一非线性问题。设 $Root[i]$ 代表只插入了原序列前 $i$ 个数所形成的权值线段树版本。显然，随着 $i$ 的递增，线段树中每个节点的频次计数 tree[u] 具有前缀和可减性（差分性）。
要求区间 $[L, R]$ 内的第 $K$ 大，我们同时让 $Root[R]$ 和 $Root[L-1]$ 两个版本的权值线段树同步进行树上二分。对于当前值域左子树：
$$cnt = tree[ls[Root[R]]] - tree[ls[Root[L-1]]]$$
这里的 $cnt$ 严格代表：在原序列区间 $[L, R]$ 内部，大小落在当前左值域区间内的元素个数。通过这个差值，我们成功将区间问题剥离并转化为全局第 $K$ 小的树上二分逻辑。
状态设计与算法推导
以经典的区间静态第 $K$ 大为例：
1. 离散化映射
原数组 $A$ 值域可能很大，首先对其进行离散化，得到有序去重数组 $raw_v$，其大小为 $U$。原数组元素全部映射为离散化后的排名下标。
2. 状态定义
Root[i]：记录插入前 $i$ 个元素后，新线段树根节点的物理编号。ls[u],rs[u]：节点 $u$ 的左右子节点编号。tree[u]：节点 $u$ 维护的值域频次和。
3. 版本推进式插入（Insert）
定义递归函数 insert(old_node, &new_node, l, r, val)：
- 申请新节点：
new_node = ++cnt; - 继承旧状态：
tree[new_node] = tree[old_node] + 1;（当前节点频次自增） - 二分推进：
- 若 $l = r$，收敛返回。
- 令 $m = (l + r) \gg 1$。若 $val \le m$，说明修改在左子树。新节点的右指针直接借用旧节点：
rs[new_node] = rs[old_node]，左指针递归创建：insert(ls[old_node], ls[new_node], l, m, val)。 - 若 $val > m$，同理借用左指针：
ls[new_node] = ls[old_node]，右指针递归：insert(rs[old_node], rs[new_node], m + 1, r, val)。
C++ 标准源码（NOIP风格）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int MAXN = 200005;
// 空间估算：静态建树 N*4 + N 次插入，每次新增 log2(N) 个节点。
// 200000 * 4 + 200000 * 18 大约需要 4.4 * 10^6 空间。直接开到 25 倍 N。
const int MAX_NODES = MAXN * 25;
int a[MAXN], raw_v[MAXN];
int Root[MAXN]; // 记录各个版本的根节点编号
int tree[MAX_NODES], ls[MAX_NODES], rs[MAX_NODES];
int cnt = 0;
// 构建版本 0 的全空静态基础树拓扑结构
int build(int l, int r) {
int u = ++cnt;
tree[u] = 0;
if (l == r) return u;
int m = (l + r) >> 1;
ls[u] = build(l, m);
rs[u] = build(m + 1, r);
return u;
}
// 核心：基于旧版本节点，推进派生新版本线段树
void insert(int old_u, int &new_u, int l, int r, int val) {
new_u = ++cnt; // 物理开辟新节点，实现路径复制
ls[new_u] = ls[old_u];
rs[new_u] = rs[old_u];
tree[new_u] = tree[old_u] + 1; // 沿途频次前缀叠加
if (l == r) return;
int m = (l + r) >> 1;
if (val <= m) {
insert(ls[old_u], ls[new_u], l, m, val); // 致命踩坑点：递归分支传入新旧节点的对应左子树指针
} else {
insert(rs[old_u], rs[new_u], m + 1, r, val); // 致命踩坑点：递归分支传入新旧节点的对应右子树指针
}
}
// 核心：双版本同步二分差分检索
int query(int u_L, int u_R, int l, int r, int k) {
if (l == r) return l;
int m = (l + r) >> 1;
// 差分计算原数组区间 [L, R] 内有多少个元素落在了当前左子树的值域区间
int left_cnt = tree[ls[u_R]] - tree[ls[u_L]];
if (k <= left_cnt) {
return query(ls[u_L], ls[u_R], l, m, k);
} else {
return query(rs[u_L], rs[u_R], m + 1, r, k - left_cnt);
}
}
int main() {
int n = read();
int m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
raw_v[i] = a[i];
}
// 离散化预处理
sort(raw_v + 1, raw_v + n + 1);
int tot = unique(raw_v + 1, raw_v + n + 1) - (raw_v + 1);
Root[0] = build(1, tot); // 生成版本 0
for (int i = 1; i <= n; ++i) {
int pos = lower_bound(raw_v + 1, raw_v + tot + 1, a[i]) - raw_v;
insert(Root[i - 1], Root[i], 1, tot, pos); // 版本 i 建立在版本 i-1 的基础之上
}
while (m--) {
int l = read(), r = read(), k = read();
// 传入版本 l-1 和版本 r 的根节点进行差分查询
int ans_idx = query(Root[l - 1], Root[r], 1, tot, k);
printf("%d\n", raw_v[ans_idx]);
}
return 0;
}
NOIP 实战避坑指南
1. 差分对位节点调用错误
在进行区间第 $K$ 大查询调用时，必须传入 Root[L - 1] 和 Root[R]。选手的低级错误常写成 query(Root[L], Root[R], ...)。因为 Root[L] 版本中已经包含了第 $L$ 个元素本身做出的贡献，如果将其减去，就会导致第 $L$ 个元素在计算时被强行开除出区间范围，引发严重的区间左端点断层数据偏小。
2. 空间上限 MAX_NODES 算错导致动态越界
可持久化线段树的空间绝对无法通过常规一维数组的 $4N$ 覆盖。由于每一次修改独立新增一条长为 $\log_2(\text{tot})$ 的独立链。空间估算应满足 $N \times 4 + N \times \lceil \log_2 N \rceil$。在 $N=2 \times 10^5$ 时，至少要开到 $N \times 24$。如果开小，++cnt 会在运行到中途时溢出数组边界，导致线上测例直接抛出 RE 或返回乱码值。
3. 指针继承遗漏
在 insert 函数中，必须一进入函数就写上 ls[new_u] = ls[old_u]; rs[new_u] = rs[old_u];。若漏掉这两行，只顾着向下递归更新变化的一侧分支，那么未变化的那一侧子树的指针将默认为 0（即变为空子树）。这会导致新版本的树拓扑结构发生大面积坏死缺失，直接丢失历史版本的全部非修改数据。
经典 NOIP/洛谷 真题
1. 洛谷 P3834 【模板】可持久化线段树 1（主席树）
- 题意描述：给定一个长度为 $N$ 的静态整数序列，有 $M$ 次询问，每次要求输出指定区间 $[L, R]$ 内的第 $K$ 小的数。
- 问题本质：区间前缀和线段树差分基准题。
- 核心解题思路：如上文源码所示。将元素做离散化值域处理，通过推进式的版本构建将“前缀”信息压缩在线段树结构中。利用 $Root[R] - Root[L-1]$ 剥离出纯粹的局部区间频次，树上二分斩获对数级 $O(\log N)$ 完美秒杀。
2. 洛谷 P4588 [TJOI2018] 异或（版本回溯综合题）
- 题意描述：维护一个集合，初始为空。支持两种操作：1. 往集合插入一个数 $X$；2. 给定一个历史时刻 $T$ 和数值 $X$，求在第 $T$ 次插入操作执行完毕后，集合中与 $X$ 异或值最大的那个数。
- 问题本质：历史版本定位 + 异或最大化问题。
- 核心解题思路：该题可以通过可持久化 Trie 树（字典树）解决，但在值域受限或采用基数拆分时，也可以利用主席树硬核破局。将每个历史时刻的集合快照保留在
Root[time]中。当面对询问时，根据给定的时刻 $T$，直接将指针锁定到Root[T]根节点上。由于该根节点完美封存了那个特定时刻的树形结构，在其内部按照 01-Trie 的高位优先贪心策略向下二分检索，可在 $O(\log \text{Val})$ 内实现完美的跨越时间维度的历史最优匹配。