主席树模板以及个人理解

主席树模板及个人理解

主席树的原理其他博客已经写的很详细了，我就不加赘述了。

主要是记录一下个人的部分理解以及模板，以便以后观看

主席树是一种可持久化数据结构，或者说，可持久化线段树，利用主席树

可以查看线段树的历史状态并对其修改

具体做法就是每个点开一颗线段树

为了节省空间采取动态开点

建树的时间复杂度是(O(nlogn))的，单次查询，插入都是(O(logn))的

总复杂度为(O((n+m)log n)) m为操作次数

下面是模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
/*主席树为了节省空间，采取的是动态开点
与动态开点相同，l，r维护的是左右儿子下标
不是区间边界 
*/
const int maxn=200010;
int T;
int n,m;
int q;
int tot;
int cnt;
int a[maxn];
int t[maxn];
int b[maxn];
struct node{
	int l,r,sum;
}tre[maxn<<5];
inline int read(){
	int f=1;
	int ret=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		ret=ret*10+(ch^'0');
		ch=getchar();
	}
	return f*ret;
}
/*
注意，build和update返回值是该树的根
所以我们的rt不能用全局变量 
*/
int build(int l,int r){
	int rt=++cnt;
	if(l==r){
		return rt;
	}
	int mid=(l+r)>>1;
	tre[rt].l=build(l,mid);
	tre[rt].r=build(mid+1,r);
	return rt;
}
/*
主席树的精髓，每一个点建一颗线段树
为了节省空间，对树进行重复利用。 
具体如何节省空间？
我们只开需要更改值的点
不需要更改值的点直接连上就好 
*/ 
int update(int t,int l,int r,int k){
	int rt=++cnt;
//	cout<<rt<<endl;
	tre[rt].l=tre[t].l; 
	tre[rt].r=tre[t].r;
	tre[rt].sum=tre[t].sum+1;//当前树继承上一颗树的状态
	if(r==l){
		return rt;
	}
	int mid=(l+r)>>1;
	if(k<=mid){
		tre[rt].l=update(tre[t].l,l,mid,k);//更改需要更改的点 
	}
	else{
		tre[rt].r=update(tre[t].r,mid+1,r,k);
	}
	return rt;	
}
int query(int le,int re,int l,int r,int k){
	if(l==r){
		return l;
	}
	int x=tre[tre[re].l].sum-tre[tre[le].l].sum;
	int mid=(l+r)>>1;
	if(x>=k){
		return query(tre[le].l,tre[re].l,l,mid,k);
	}//求区间第k大，因为维护的区间是有序的，所以加入左区间点数大于k，那么区间第k大一定在左侧 
	else{
		return query(tre[le].r,tre[re].r,mid+1,r,k-x);
	}
}
int main(){
	freopen("P3834_9.in","r",stdin);
		n=read();
		q=read();
		for(int i=1;i<=n;i++){
			a[i]=read();
			b[i]=a[i];
		}
		m=unique(b+1,b+1+n)-b-1;//为什么我们需要减1？数组首元素需要考虑
		sort(b+1,b+1+n);
		t[0]=build(1,m);
		for(int i=1;i<=m;i++){
			a[i]=lower_bound(b+1,b+1+m,a[i])-b;
			t[i]=update(t[i-1],1,m,a[i]);
		}
		int x,y,z;
		while(q--){
			x=read();
			y=read();
			z=read();
			int p=query(t[x-1],t[y],1,m,z);
			cout<<b[p]<<endl;
		}
	return 0;
}