可持久化线段树

作者： beijian / 2023年3月4日

什么是可持久化线段树

普通线段树每次修改都会”破坏”旧版本，而可持久化线段树（也称主席树）支持查询任意历史版本。核心技巧是路径复制：每次修改只新建从根到目标叶子路径上的 O(log n) 个节点，其余节点与旧版本共享。这样既保留了完整历史，空间也只有 O(n log n)。

核心思想

版本 = 根节点：每个版本有一个独立的根，通过根可以访问该版本的整棵树；
路径复制：修改时复制”根 → 叶子”路径上的节点，新节点与旧节点共享未修改的子树；
版本相减：结合前缀和思想，版本R 减去版本L-1 就能得到区间 [L, R] 的统计信息——这是求区间第 K 小/大的基础。

复杂度

每次修改/查询：O(log n)；
空间：O(n log n)（n 次操作各产生 O(log n) 个新节点）。

C++ 实现：区间第 K 小（静态主席树）

1. 结构定义与离散化


const int N = 1e5 + 10;
const int M = N * 20;      // 节点数估计：N * logN

struct Node { int l, r, sum; } tr[M];  // 左右子树下标 + 计数
int root[N], idx;                      // 各版本根 + 节点计数器
vector<int> nums;                      // 离散化数组

int get_id(int x) {                    // 值 → 排名(1..m)
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
}

2. 建初始空树与更新


int build(int l, int r) {              // 建空树（值域 [l,r]）
    int p = ++idx;
    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 x) {  // 在版本 p 基础上插入 x，返回新版本
    int q = ++idx;
    tr[q] = tr[p];                     // 复制旧节点（共享未修改子树）
    if (l == r) { tr[q].sum++; return q; }
    int mid = (l + r) >> 1;
    if (x <= mid) tr[q].l = update(tr[p].l, l, mid, x);
    else          tr[q].r = update(tr[p].r, mid + 1, r, x);
    tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
    return q;
}

3. 区间第 K 小查询


// 在"版本 q 减版本 p"的值域树上找第 k 小
int query(int p, int q, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int cnt = tr[tr[q].l].sum - tr[tr[p].l].sum;  // 左子树在区间内的元素个数
    if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
    else          return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

4. 主流程


int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    nums = a;
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    root[0] = build(1, nums.size());              // 空版本
    for (int i = 1; i <= n; i++)                  // 版本 i = 前 i 个数
        root[i] = update(root[i-1], 1, nums.size(), get_id(a[i-1]));

    while (m--) {
        int l, r, k; scanf("%d%d%d", &l, &r, &k);
        int pos = query(root[l-1], root[r], 1, nums.size(), k);
        printf("%dn", nums[pos-1]);              // 排名还原为原值
    }
    return 0;
}

应用场景

静态区间第 K 大/小：版本相减，经典主席树题（POJ 2104 等）；
可持久化数组：支持回到历史版本做单点修改和查询；
二维数点：配合扫描线，把”矩形内点数”转成区间查询；
动态区间第 K 小：外层再套树状数组（树套树）。

优化技巧

动态开点：不必预先分配 M 个节点，按需创建，适合值域大、操作少的情况；
内存池：用数组下标代替指针，避免动态分配的开销与碎片；
注意 M 的大小：节点总数 = 初始空树 + n×log(值域)，开太小会数组越界（这是主席树最常见的 RE 原因）。