可持久化线段树（主席树）提高组

💡 核心思想

可持久化线段树（又称主席树）是在每次修改时保留历史版本的线段树。通过"路径复制"技巧：每次修改只创建 O(log n) 个新节点，其余节点共享原树的节点。这样可以在 O(log n) 时间内查询任意历史版本。经典应用：区间第 K 大（静态）、区间修改的历史版本查询。

🎯 直觉理解

想象你在写一份重要文档，每次修改前都先"另存为"一个新版本。普通做法是复制整份文档（O(n)），而主席树的做法是：只复制你修改的那几页（O(log n)），其他页直接引用旧版本。这样你就有了一份完整的历史版本库，可以随时回到任意版本查看。

📝 算法流程

1. 建立权值线段树（按值域而非下标）
2. 每次修改（单点更新）：
3. 创建新根节点
4. 递归修改：被修改的子树创建新节点，另一个子树直接指向原节点
5. 查询区间 [l,r] 的第 K 大：
6. 用 root[r] 和 root[l-1] 两个版本同时查询
7. 左子树的节点数差 = 区间中落在左子树的数的个数
8. 如果 >= K，递归左子树；否则递归右子树，K 减去左子树个数

$$\text{节点数：}O(n \log n)\text{（每次修改新增 }\log n\text{ 个节点）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

const int N = 200005;
struct Node { int l, r, sum; } tr[N * 20];
int root[N], cnt;
int a[N], b[N]; // b 为离散化后的值

int build(int l, int r) {
    int p = ++cnt;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}

int update(int p, int l, int r, int pos) {
    int q = ++cnt;
    tr[q] = tr[p]; tr[q].sum++;
    if (l == r) return q;
    int mid = (l + r) >> 1;
    if (pos <= mid) tr[q].l = update(tr[p].l, l, mid, pos);
    else tr[q].r = update(tr[p].r, mid + 1, r, pos);
    return q;
}

int query(int p, int q, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int leftSum = tr[tr[q].l].sum - tr[tr[p].l].sum;
    if (leftSum >= k) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - leftSum);
}

int main() {
    int n = 5, m = 5;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 离散化
    memcpy(b, a, sizeof(a));
    sort(b + 1, b + n + 1);
    int sz = unique(b + 1, b + n + 1) - (b + 1);
    
    root[0] = build(1, sz);
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(b + 1, b + sz + 1, a[i]) - b;
        root[i] = update(root[i-1], 1, sz, pos);
    }
    
    // 查询 [l,r] 第 k 大
    cout << b[query(root[0], root[n], 1, sz, 3)] << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目