#创作计划#主席树，优美的数据结构
2025-10-26 18:44:24
发布于：广东
快要考CSP了，还不会主席树？赶紧学习一下这个充满魅力的数据结构吧
主席树的使用范围
主席树被用于求解无增删可持续化区间操作的维护以及动态区间第k小值上。
主席树的思想
当我们对一个数据结构进行可持续化时，如果对所有历史版本进行保存空间，复杂度会很高。因此我们可以使用可持续化线段树维护线性或树形数据结构，可持续化线段树又称主席树。
学习主席树的思想前，请学习前缀和思想、共用点、离散化、权值线段树、动态开点等知识。
以区间第k小值这个问题为例。
权值线段树可以对单个区间进行值域统计，其原理是先对数据进行离散化，再维护每个数出现的次数。如图（画图好难用啊啊啊）：
注意到权值线段树仅能维护一个区间。
考虑进行可持续化，如果我们对于从到的每个数i建一个维护区间 ~ 的权值线段树，当我们需要查询 ~ 的第k小数时，对于每个节点，将其在的版本的值减去其在版本的大值，通过对差分的简单思考可知其正确性。
但是如果对于每一个元素都建一颗大小为（为去重离散化后数组大小）的权值线段树，空间复杂度为，轻而易举MLE（跑完几十个数据点空间超崩铁了）
接下来（划重点）是主席树的核心思想：
----------------------动态开点-----------------------
怎么可能
并不是动态开点。但是记住动态开点是开一个结构体（空间更多了啊喂）存储线段树左端点和右端点在大胃袋数组中的编号以便查找（++cnt)，代码中将以实参函数的方式实现，《算法竞赛》中有返回值函数示例，欢迎诸位比我更蒟蒻的OIer参考。
主席树的核心思想是：存储链条。
种植一棵线段树，观察其生长过程，注意到权值线段树一开始是全是0的成都树空树，每次modify操作后，其结构有且仅有一条从叶子节点到根节点的链上的值发生改变。考虑对于每次操作存储链。
每次查询依旧用差分思想进行。
代码：
以下是本题代码：
建新树（当时使用了返回值，后来发现不如实参香，将就着看吧）：
int build(int la,int pl,int pr,int p){
int ran=++cnt;
tree[cnt].l=tree[la].l;
tree[cnt].r=tree[la].r;
tree[ran].v=tree[la].v+1;
int mid=pl+pr>>1;
if(pl<pr){
if(p<=mid)
tree[ran].l=build(tree[la].l,pl,mid,p);
else
tree[ran].r=build(tree[la].r,mid+1,pr,p);
}
return ran;
}
查询：
int query(int ll,int rr,int pl,int pr,int x){
if(pl==pr)return pl;
int k=tree[tree[rr].l].v-tree[tree[ll].l].v;
int mid=pl+pr>>1;
if(x>k)
return query(tree[ll].r,tree[rr].r,mid+1,pr,x-k);
else
return query(tree[ll].l,tree[rr].l,pl,mid,x);
}
离散化+初始化：
sort(b+1,b+n+1);
int ttl=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)
root[i]=build(root[i-1],1,ttl,lower_bound(b+1,b+ttl+1,a[i])-b);
查询（细节\n加速）：
cout<<b[query(root[L-1],root[R],1,ttl,K)]<<"\n";
所有代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int n,m,a[N],b[N],root[N],cnt,L,R,K;
struct{
int l,r,v;
}tree[N<<5];
int build(int la,int pl,int pr,int p){
int ran=++cnt;
tree[cnt].l=tree[la].l;
tree[cnt].r=tree[la].r;
tree[ran].v=tree[la].v+1;
int mid=pl+pr>>1;
if(pl<pr){
if(p<=mid)
tree[ran].l=build(tree[la].l,pl,mid,p);
else
tree[ran].r=build(tree[la].r,mid+1,pr,p);
}
return ran;
}
int query(int ll,int rr,int pl,int pr,int x){
if(pl==pr)return pl;
int k=tree[tree[rr].l].v-tree[tree[ll].l].v;
int mid=pl+pr>>1;
if(x>k)
return query(tree[ll].r,tree[rr].r,mid+1,pr,x-k);
else
return query(tree[ll].l,tree[rr].l,pl,mid,x);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
int ttl=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)
root[i]=build(root[i-1],1,ttl,lower_bound(b+1,b+ttl+1,a[i])-b);
while(m--){
cin>>L>>R>>K;
cout<<b[query(root[L-1],root[R],1,ttl,K)]<<"\n";
}
return 0;
}
我们需要更多主席树
依旧更多主席树：
P3919 【模板】可持久化线段树 1（可持久化数组）
P4137 Rmq Problem / mex
因为过于蒟蒻所以只会这几题+注意到主席树常数很大，空间复杂度也能把ST表击败，只能跑的数据，加上结合其它知识点难度较大，还是高贵的可持续化，所以洛谷题不多
本来此优秀算法可以跑教主，但是教主的太大了，主席树需要建树，常数大跑不了，分块复杂度是，主要为的大小主导，杯壁的教主开了个很小的，加上这个查询肯定没跑满构造，所以现在唯一解是分块。
题解
可持续化数组这题，只需关注叶子节点的值，运用普通线段树技巧可以完成。注意用i遍历能很方便地进行时间增加操作，加上数组为初始即得，所以添加一个建全树的函数build,update用于开链树（好像只有我一个人这么叫它）
（快读快写+实参版本）:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const int N=1000005;
struct node{
int l,r,v;
}tree[N*45];
int n,m,root[N],a[N],cnt;
void build(int &u,int pl,int pr){
u=++cnt;
if(pl==pr){tree[u].v=a[pl];return;}
int mid=pl+pr>>1;
build(tree[u].l,pl,mid);
build(tree[u].r,mid+1,pr);
}
void update(int &cur,int la,int pl,int pr,int p,int x){
cur=++cnt;
tree[cur]=tree[la];
if(pl==pr){
tree[cur].v=x;
return;
}
int mid=pl+pr>>1;
if(p<=mid)update(tree[cur].l,tree[la].l,pl,mid,p,x);
else update(tree[cur].r,tree[la].r,mid+1,pr,p,x);
}
int query(int pl,int pr,int p,int x){
if(pl==pr)return tree[p].v;
int mid=pl+pr>>1;
if(x<=mid)return query(pl,mid,tree[p].l,x);
return query(mid+1,pr,tree[p].r,x);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
build(root[0],1,n);
for(int i=1;i<=m;++i){
int t=read(),op=read(),po=read();
if(op==1){
int k=read();
update(root[i],root[t],1,n,po,k);
}
else{
root[i]=root[t];
write(query(1,n,root[t],po));
putchar('\n');
}
}
return 0;
}
此题原用莫队，疯改回滚而灵机一动，提交题解发现题解亦不可过，故Hjted之（指主席树发明人黄嘉泰）
需要进行一定的思考，考虑修改当前权值对应的“最后一次出现的位置”为当前位置（参考题解原话），答案就是第棵线段树上，第一个“最后一次出现的位置”小于的权值。（不是抄袭，原题解的表达比较适合描述算法就拿来用了，原作者）
:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const int N=200005;
int n,m,a,root[N],cnt,L,R;
struct node{int ls,rs,v;}ts[N<<5];
void push_up(int x){ts[x].v=min(ts[ts[x].ls].v,ts[ts[x].rs].v);}
void update(int &rt,int la,int ll,int rr,int p,int x){
rt=++cnt;
ts[rt]=ts[la];
if(ll==rr){
ts[rt].v=x;
return;
}
int mid=ll+rr>>1;
if(p<=mid)update(ts[rt].ls,ts[la].ls,ll,mid,p,x);
else update(ts[rt].rs,ts[la].rs,mid+1,rr,p,x);
push_up(rt);
}
int query(int ll,int rr,int k,int p){
if(ll==rr)return ll;
int mid=ll+rr>>1;
if(ts[ts[p].ls].v<k)return query(ll,mid,k,ts[p].ls);
else return query(mid+1,rr,k,ts[p].rs);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
a=read();
if(a>200000)root[i]=root[i-1];
else update(root[i],root[i-1],0,N,a,i);
}
for(int i=1;i<=m;++i){
L=read(),R=read();
write(query(0,N,L,root[R]));putchar('\n');
}
return 0;
}
重要的结尾
这么精心的文章不给个赞吗，诅咒所有不收藏的人CSP-S考到主席树（
有帮助，赞一个