# 主席树 (可持续化权值线段树)

可持续化系列的一种数据结构,可以保存修改的版本,本质上是一种可持续化权值线段树

# 区间第 k 小

倘若不是区间,而是每次求所有值的第 k 小,一个权值线段树就搞定了,将所有数离散化一下,将数值作为插入位置建树,之后查询第 k 小时,如果左子树插入点数量大于 k 就在右子树上,否则就在左子树上,这样就能第 k 小的数在排好序的数组中排第几个了,每次修改花费 logn 时间,查询也花费 logn 时间

而如果现在变成了区间第 k 小,单纯的线段树就维护不了了,因为无法保存过去的信息,如果可以保存过去没有修改过的信息就好了,(每次修改都建一颗新树,空间炸不炸呀),其实容易想到修改一个点后,变动的点只是这个点的所有祖宗节点(包括父亲节点),只有 logn 个(n 个点的树深度最多是 logn),所以可以拉出来一条链来保存修改过的信息

image-20210410213123576

如图,红色的链就是修改过的信息

image-20210410213503619

主席树因为要保存版本信息,无法用 2*id 表示左孩子那种方式建树,要用朴素的 lson 和 rson 数组表示左右孩子

# 个人理解

主席树本质就是前缀权值线段树,权值线段树保存的是每一个区间的值的个数,而主席树就是对每一个前缀都建了一棵树,只不过是优化了空间,并没有真的建出一棵树,在一棵树上拉出了几条链,查询区间第 k 小时,就用 r 版本的树减去 l-1 版本的树,得到的就是这个区间的树

# 洛谷 P3834

#include <bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int lson,rson,sum;
}hjt[MAXN*5];
struct name{
	int id,val,fak;
}arr[MAXN];
int bak[MAXN];
int root[MAXN*5];
int n,m,k,cnt,mid;
bool cmp1(name a,name b){
	return a.val<b.val;
}
bool cmp2(name a,name b){
	return a.id<b.id;
} 
int build(int l,int r){
	int rt=++cnt;  // 分配空间 
	if(l==r) return rt;  // 如果这个节点是叶子节点 (不是管理员) 就返回这个节点的编号 
	int mid=l+r>>1;
	hjt[rt].lson=build(l,mid);  // 建立这个节点的左子树 
	hjt[rt].rson=build(mid+1,r);
	return rt;  // 返回根节点 
}
int insert(int pre,int l,int r,int pos){
	int rt=++cnt;  // 分配空间
	hjt[rt]=hjt[pre];  // 在前一个版本的基础上建树
	hjt[rt].sum++;  // 当前版本多了一个值 
	if(l==r)  return rt;  // 叶子节点直接返回,表示已经建好当前版本了
	mid=(l+r)>>1;
	if(pos<=mid) hjt[rt].lson=insert(hjt[pre].lson,l,mid,pos);
	else hjt[rt].rson=insert(hjt[pre].rson,mid+1,r,pos); 
	return rt;
}
int query(int u,int v,int l,int r,int k){
	if(l==r) return l;
	int cha=hjt[hjt[v].lson].sum-hjt[hjt[u].lson].sum;
	int mid=l+r>>1;
	if(cha>=k) return query(hjt[u].lson,hjt[v].lson,l,mid,k);
	else return query(hjt[u].rson,hjt[v].rson,mid+1,r,k-cha);
}
int main(){
	ios;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>arr[i].val;
		bak[i]=arr[i].val;
		arr[i].id=i;
	}
	sort(bak+1,bak+1+n);
	sort(arr+1,arr+1+n,cmp1);
	for(int i=1;i<=n;i++) arr[i].fak=i;
	sort(arr+1,arr+1+n,cmp2);
	root[0]=build(1,n);
	for(int i=1;i<=n;i++) root[i]=insert(root[i-1],1,n,arr[i].fak);
//	for(int i=0;i<=n;i++) cout<<hjt[root[i]].sum<<' ';
//	cout<<'\n';
	while(m--){
		int l,r;
		cin>>l>>r>>k;
		cout<<bak[query(root[l-1],root[r],1,n,k)]<<'\n';
	}
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝