可持久化线段树（主席树）入门

一、基础概念与引入

1.1 什么是可持久化数据结构

可持久化数据结构（Persistent Data Structure）是一种能够保存其所有历史版本的数据结构。每次修改操作都会创建一个新的版本，而不是覆盖原有版本。这种特性使得我们可以：

回退到任意历史状态
同时访问多个版本
支持高效的区间查询历史信息

1.2 主席树的由来

可持久化线段树通常被称为"主席树"，这个名字来源于我国的国家队选手黄嘉熹（主席）。他最早在国内普及这种数据结构的应用。

1.3 核心思想

普通线段树每次修改会改变 O(log n) 个节点。主席树的核心思想是：

复用未修改的节点：只创建被修改路径上的新节点
保留根节点历史：每个版本都有独立的根节点指针
空间复杂度：O(n log n)，每次修改增加 O(log n) 个节点

—

二、算法原理与核心思想

2.1 构建过程

初始版本（空树）：
    root[0]

插入第 i 个元素：
    从 root[i-1] 复制一条路径
    修改路径上的节点计数
    其他节点直接复用

2.2 版本控制示意图

版本1:    A
         /         B   C (复用)
       /       D   E (复用)

版本2:    A'
         /         B'  C (复用)
       /       D'  E (复用)

2.3 关键性质

每个版本独立：修改不会影响历史版本
空间高效：只增量存储变化部分
时间不变：单次操作仍是 O(log n)

—

三、C++ 完整实现代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int LOG = 20;  // 足够容纳 1e5 的空间

struct Node {
    int l, r;        // 左右子节点编号
    int cnt;         // 区间内元素个数
} tree[MAXN * LOG];  // 主席树数组

int root[MAXN];     // 各版本根节点编号
int cnt;            // 节点分配计数器

// 建树函数（初始空树）
int build(int l, int r) {
    int node = ++cnt;
    if (l == r) {
        tree[node].cnt = 0;
        return node;
    }
    int mid = (l + r) >> 1;
    tree[node].l = build(l, mid);
    tree[node].r = build(mid + 1, r);
    tree[node].cnt = tree[tree[node].l].cnt + tree[tree[node].r].cnt;
    return node;
}

// 更新函数：创建新版本
// prev: 前一版本节点
// l, r: 当前区间
// pos: 要插入的位置
int update(int prev, int l, int r, int pos) {
    int node = ++cnt;  // 创建新节点
    tree[node] = tree[prev];  // 复制前一版本信息
    
    if (l == r) {
        tree[node].cnt++;
        return node;
    }
    
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        // 左子树需要修改，递归更新左子树
        tree[node].l = update(tree[prev].l, l, mid, pos);
    } else {
        // 右子树需要修改，递归更新右子树
        tree[node].r = update(tree[prev].r, mid + 1, r, pos);
    }
    
    // 更新当前节点计数
    tree[node].cnt = tree[tree[node].l].cnt + tree[tree[node].r].cnt;
    return node;
}

// 查询函数：求区间 [L, R] 中第 k 小
// u: 第 L-1 版本根节点
// v: 第 R 版本根节点
// l, r: 当前区间
// k: 第 k 小
int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    
    int mid = (l + r) >> 1;
    int left_cnt = tree[tree[v].l].cnt - tree[tree[u].l].cnt;
    
    if (left_cnt >= k) {
        // 第 k 小在左子树
        return query(tree[u].l, tree[v].l, l, mid, k);
    } else {
        // 第 k 小在右子树
        return query(tree[u].r, tree[v].r, mid + 1, r, k - left_cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n + 1);
    vector<int> all;  // 用于离散化
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        all.push_back(a[i]);
    }
    
    // 离散化
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    int size = all.size();
    
    // 初始化
    cnt = 0;
    root[0] = build(1, size);
    
    // 构建各个版本
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
        root[i] = update(root[i - 1], 1, size, pos);
    }
    
    // 处理查询
    while (m--) {
        int L, R, k;
        cin >> L >> R >> k;
        int ans_pos = query(root[L - 1], root[R], 1, size, k);
        cout << all[ans_pos - 1] << '\n';
    }
    
    return 0;
}

—

四、经典例题

例题1：区间第 k 小（静态区间）

题目描述
给定长度为 n 的序列 a，有 m 次查询，每次查询 [L, R] 中的第 k 小元素。
n ≤ 1e5，m ≤ 1e5。

解题思路
这是主席树最经典的应用场景：

将数值离散化到 [1, size]
按顺序插入每个元素，建立 n 个版本
版本 R 减去版本 L-1 就是区间 [L, R] 的信息
通过比较左右子树差值，确定第 k 小位置

完整代码

// 同上面的完整实现代码
// 输入示例：
// 5 3
// 3 1 4 2 5
// 1 5 3  -> 输出 3
// 2 4 2  -> 输出 2
// 1 3 2  -> 输出 3

—

例题2：区间不同数个数

题目描述
给定序列 a，多次查询区间 [L, R] 中不同数的个数。
n ≤ 1e5，m ≤ 1e5。

解题思路

记录每个数上一次出现的位置 pre
按位置 i 建立主席树，插入 pre+1
查询 [L, R] 时，查询第 R 个版本中 ≤ L 的个数

完整代码

// 核心思路：
// 对于每个位置 i，插入值为 pre[i]+1
// 查询区间 [L, R] 时，统计 <= L 的数量
// 这个数量就是区间内不同数的个数

int pre[MAXN];  // pre[i] 表示 a[i] 上一次出现的位置
int last[MAXN]; // last[v] 表示值 v 最后出现的位置

// 构建时：root[i] = update(root[i-1], pre[i]+1, 1)
// 查询时：query(root[R], 1, L) - query(root[L-1], 1, L)

—

例题3：可持久化权值线段树求中位数

题目描述
给定序列 a，支持两种操作：

查询区间 [L, R] 的中位数
修改某个位置的值
n ≤ 1e5，m ≤ 1e5。

解题思路

中位数即第 (R-L+1+1)/2 小的数
使用可持久化线段树维护权值信息
对于修改操作，需要建立新的版本

完整代码

// 查询中位数：
int len = R - L + 1;
int k = (len + 1) / 2;  // 中位数位置
int median = query(root[L-1], root[R], 1, size, k);
cout << all[median - 1] << endl;

—

五、时间/空间复杂度分析

5.1 时间复杂度

操作	复杂度	说明
建树	O(n)	普通线段树建树
更新	O(log n)	每次修改 O(log n) 个节点
查询	O(log n)	二分查找第 k 小

5.2 空间复杂度

理论上限：O(n log n)
实际估算：n = 1e5 时，需要约 2e6 个节点
优化建议：
- 使用指针数组代替结构体数组
- 动态分配内存（但数组更快）
- 离散化压缩数值范围

5.3 与其他数据结构对比

方法	空间	时间(查询)	时间(修改)	支持在线
主席树	O(n log n)	O(log n)	O(log n)	✓
莫队	O(n√n)	O(√n)	-	✗
划分树	O(n log n)	O(log n)	-	✓
归并树	O(n log n)	O(log² n)	-	✓

—

六、学习路径与进阶建议

6.1 入门阶段（1-2周）

理解概念：
- 为什么需要可持久化？
- 节点复用原理是什么？
- 版本之间如何关联？
模板练习：
- 手写至少 3 遍主席树模板
- 理解每个参数的含义
- 调试边界情况
基础题目：
- 区间第 k 小（必做）
- 区间不同数个数
- 区间中位数

6.2 进阶阶段（2-3周）

扩展应用：
- 可持久化字典树
- 可持久化并查集
- 可持久化平衡树
复杂题目：
- 树上路径第 k 小
- 带修主席树
- 可持久化线段树合并
优化技巧：
- 空间优化
- 常数优化
- 边界处理

6.3 高阶应用（长期）

组合应用：
- 主席树 + 树链剖分
- 主席树 + CDQ 分治
- 主席树 + 后缀自动机
比赛实战：
- CF Div1 C/D 题
- NOI/NOIP 真题
- ICPC 区域赛题目

6.4 学习资源推荐

博客文章：
- 「主席树」入门到入土系列
- OI Wiki 可持久化线段树
- 洛谷题解精选
题目列表：
- 洛谷 P3834 【模板】可持久化线段树 1
- 洛谷 P3567 [POI2014] KUR-Courses
- HDU 2665 Kth number
- BZOJ 2120 数颜色
视频教程：
- B站算法可视化系列
- AcWing 提高课

—

总结：主席树是信息学竞赛中最重要的数据结构之一，掌握它能解决一大类区间查询问题。关键在于理解"复用节点、保留历史"这一核心思想，然后通过大量练习来熟练掌握。