主席树与可持久化数据结构：原理、模板及应用详解

可持久化数据结构能在修改操作后保留历史版本，本文重点介绍主席树。

一、可持久化思想
每次修改不直接修改原结点，而是新建一部分结点，共享未修改的部分。这样每个版本的根节点就能访问该版本的所有数据。

二、主席树（可持久化权值线段树）
最经典的应用：静态区间第 k 小。

核心思想：

• 对序列的前缀建立权值线段树


• 第 i 棵线段树表示前 i 个数的分布


• 区间 [L, R] = 第 R 棵 - 第 L-1 棵


• 通过二分找到第 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 = sum[lc[v]] - sum[lc[u]];
    if (k <= x) return query(lc[u], lc[v], l, mid, k);
    else return query(rc[u], rc[v], mid + 1, r, k - x);
}

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


• 可持久化 Trie（可持久化 01-Trie）


• 可持久化并查集（可撤销 + 主席树）


• 可持久化平衡树（如可持久化 FHQ Treap）

1. 静态区间第 k 小（经典）


2. 动态区间第 k 小（树状数组套主席树）


3. 树上路径第 k 小（树上主席树）


4. 区间不同数的个数（离线/在线）

• 洛谷 P3834 静态区间第 k 小


• 洛谷 P2617 动态区间第 k 小（树套树）


• 洛谷 P2633 树上路径第 k 小