主席树 学习笔记

主席树

主席树就是权值线段树的一个集合；

模板题为求某个区间的第 K 大，权值线段树也有求第 K 大这个功能，但是不能维护区间，只能求整个全局第 K 大；

所以学习这个之前，务必先搞懂权值线段树；

所以代码都是这道题的；

【模板】可持久化线段树 1（主席树）

1、先从建树开始说起：

int build(int l,int r){
	int rt=++root;
	int d=(l+r)>>1;
	if(l<r){
		L[rt]=build(l,d);
		R[rt]=build(d+1,r);
	}
	return rt;
}

这个建树和线段树是不一样的，我没有用结构体建树，因为我认为线段树用结构体建树，结构体里面的 l，r 是区间边界，而主席树是左儿子和右儿子，会搞混，所以直接用L，R；

这个建树没有利用二叉树的性质（当父节点是k，左儿子是2* k 右儿子是2*k+1）;而是直接先序遍历，记录一个节点的左右儿子结点；这样建树的好处在于方便后面加链；

2、更新操作

int update(int pre,int l,int r,int pos){
	int rt=++root;
	L[rt]=L[pre],R[rt]=R[pre],sum[rt]=sum[pre]+1;
	int d=(l+r)>>1;
	if(l<r){
		if(pos<=d) L[rt]=update(L[pre],l,d,pos);
		else R[rt]=update(R[pre],d+1,r,pos);
	}
	return rt;
}

个人认为，更新操作就是主席树的精髓所在，每次插入一个值，相当于又建一颗权值线段树，但是这个又建并不是又开数组重新建一个，而是在原先的基础上再加一条链，这个不好理解，建议配合图片和代码理解；

3、查询操作

int query(int pre,int nw,int l,int r,int k){//第k大 
	if(l==r) return l;
	int s=sum[L[nw]]-sum[L[pre]];//左子树值 
	int d=(l+r)>>1;
	if(s>=k) return query(L[pre],L[nw],l,d,k);
	else return query(R[pre],R[nw],d+1,r,k-s); 
}

这个就是权值线段树的思想了，当左子树的值大于 k 时，说明左子树一定存在解，反之，遍历右子树；

但是这里最关键的是左子树的值怎么获取，主席树就体现出来了；

总的代码：

#include<bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=200100;
const int M=10000000;
const ll mod=100000000;
int n,m,a[N],b[N],c[N],ans[N],tr[N],L[N*40],R[N*40],sum[N*40],root;
int build(int l,int r){
	int rt=++root;
	int d=(l+r)>>1;
	if(l<r){
		L[rt]=build(l,d);
		R[rt]=build(d+1,r);
	}
	return rt;
}
int update(int pre,int l,int r,int pos){
	int rt=++root;
	L[rt]=L[pre],R[rt]=R[pre],sum[rt]=sum[pre]+1;
	int d=(l+r)>>1;
	if(l<r){
		if(pos<=d) L[rt]=update(L[pre],l,d,pos);
		else R[rt]=update(R[pre],d+1,r,pos);
	}
	return rt;
}
int query(int pre,int nw,int l,int r,int k){//第k大 
	if(l==r) return l;
	int s=sum[L[nw]]-sum[L[pre]];//左子树值 
	int d=(l+r)>>1;
	if(s>=k) return query(L[pre],L[nw],l,d,k);
	else return query(R[pre],R[nw],d+1,r,k-s); 
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	b[i]=a[i];
	}
	sort(a+1,a+n+1);
	int cnt=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
		ans[c[i]]=b[i];
	}
	tr[0]=build(1,cnt);
	for(int i=1;i<=n;i++){
		tr[i]=update(tr[i-1],1,cnt,c[i]);
	}
	while(m--){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<ans[query(tr[l-1],tr[r],1,cnt,k)]<<endl;
	} 
    return 0;
}