主席树全面介绍：
主席树，全称可持久化线段树（ Persistent Segment Tree ），是由中国选手黄嘉泰（ID:主席）在2012年提出的一种高级数据结构，因此得名"主席树"。
它是一种革命性的数据结构，完美解决了传统线段树无法保存历史版本的缺陷。
1.1 核心思想
主席树的核心在于 “版本控制” 和 “节点复用” 。
与传统线段树每次更新都破坏原有结构不同，主席树采用以下策略：
-
- 路径复制：当需要修改某个节点时，不直接修改原节点，而是创建它的副本
-
- 结构共享：新旧版本共享未被修改的子树结构
-
- 版本链：通过根节点数组维护各个版本的入口
这种设计使得：
-
每个版本 独立存在且不可变
-
空间复杂度优化到 O(n log n)
-
查询效率保持 O(log n)
1.2 技术实现细节
主席树的实现基于以下几个关键技术点：
离散化处理：
sort ( nums.begin ( ) , nums.end ( ) );
nums.erase ( unique ( nums.begin ( ) , nums.end ( ) ) , nums.end ( ) );
将原始数据映射到紧凑的整数区间，减少存储需求。
动态开点：
int p = ++idx;
tr [p] = { l , r , 0 };
按需创建节点而非预先分配完整结构。
版本管理：
root [new_ver] = insert ( root [old_ver] , ... );
通过根节点数组维护版本链。
1.3 复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建空树 | O(n) | O(n) |
| 单点更新 | O(log_n) | O(log_n) |
| 区间查询 | O(log_n) | O(1) |
| 历史版本查询 | O(log_n) | O(1) |
1.4 变种与扩展
- 带修改主席树：结合树状数组实现动态更新
- 二维主席树：处理二维平面问题
- 可持久化数组：基于主席树实现
- 可持久化并查集：支持历史版本回溯
2. 完整模板代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int LOG = 20;
struct node
{
struct Node
{
int lc;
int rc;
int sum;
} tr[MAXN * LOG];
vector < int > roots;
vector < int > nums;
int idx;
void init ( const vector < int > & orig)
{
nums = orig;
sort ( nums.begin ( ) , nums.end ( ) );
nums.erase ( unique ( nums.begin ( ) , nums.end ( ) ) , nums.end ( ) );
idx = 0;
roots.push_back ( build ( 0 , nums.size ( ) - 1 ) );
}
int build ( int l , int r )
{
int p = ++idx;
tr [p] = { 0 , 0 , 0 };
if ( l == r )
{
return p;
}
int mid = ( l + r ) >> 1;
tr [p].lc = build ( l , mid );
tr [p].rc = build ( mid + 1 , r );
return p;
}
int update (int prev , int l , int r , int x , int val )
{
int p = ++idx;
tr[p] = tr [prev];
if ( l == r )
{
tr [p].sum += val;
return p;
}
int mid = ( l + r ) >> 1;
if ( x <= mid )
{
tr [p].lc = update (tr [prev].lc , l , mid , x , val );
}
else
{
tr [p].rc = update ( tr[prev].rc , mid + 1, r , x , val );
}
tr [p].sum = tr [tr [p].lc].sum + tr [tr [p].rc].sum;
return p;
}
int query ( int u , int v , int l , int r , int k )
{
if ( l == r )
{
return l;
}
int left_cnt = tr [tr [v].lc].sum - tr [tr [u].lc].sum;
int mid = ( l + r ) >> 1;
if ( k <= left_cnt )
{
return query ( tr [u].lc , tr [v].lc , l , mid , k );
}
else
{
return query ( tr [u].rc , tr [v].rc , mid + 1 , r , k - left_cnt );
}
}
void add_version ( int x )
{
int pos = lower_bound ( nums.begin ( ) , nums.end ( ), x ) - nums.begin ( );
roots.push_back ( update ( roots.back ( ) , 0 , nums.size ( ) - 1, pos, 1 ) );
}
int get_kth ( int l , int r , int k )
{
return nums [query ( roots [l - 1] , roots [r] , 0 , nums.size ( ) - 1 , k )];
}
};
int main()
{
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, m;
cin >> n >> m;
vector < int > ar(n);
for ( int i = 0; i < n; i ++ )
{
cin >> ar[i];
}
node pst;
pst.init(ar);
for ( int x : ar )
{
pst.add_version(x);
}
while ( m -- )
{
int l;
int r;
int k;
cin >> l >> r >> k;
cout << pst.get_kth(l, r, k) << '\n';
}
return 0;
}
3. 经典例题：区间第K小
问题描述：给定长度为 N 的序列和 M 个查询，每个查询求区间 [L, R] 中第 K 小的数。
解题思路：
-
离散化原始数据
-
建立前缀主席树，每个位置 i 对应 $[1,i]$的版本
-
查询 [L,R] 时，用 R 版本减去 L-1 版本得到区间统计
-
在合并后的树上进行二分查找
复杂度分析：
-
预处理：O(N log N)
-
单次查询：O(log N)
4. 应用场景扩展
-
区间不同元素计数：
-
记录每个元素最后出现位置
-
主席树维护位置信息
-
-
历史版本恢复：
-
保存每次操作后的版本
-
支持回溯到任意历史状态
-
-
二维数点问题：
-
对一维排序
-
另一维用主席树维护
-
-
带修改区间查询：
-
结合树状数组
-
实现 O(log_²N) 的更新和查询
-
主席树以其优雅的设计和强大的功能，已经成为现代算法竞赛中不可或缺的高级数据结构。掌握主席树不仅能解决特定问题，更能培养对数据结构的深刻理解。
最后：
如果您认为这个帖子对你有帮助，请务必点一个赞，谢谢，Thanks♪(･ω･)ﾉ，您的支持是我创作的最大动力。
您认为这个帖子对您的帮助
- 帮助很大
- 有帮助
- 有一点帮助
- 一般般
- 没有帮助
- 有点差
- 很差
- 非常差
Thanks♪(･ω･)ﾉ观看
ヾ(￣▽￣)Bye~Bye~