可持久化线段树（主席树）

可持久化线段树（主席树）

定义

• 可持久化线段树，又称函数式线段树，是最重要的可持久化数据结构之一。
• 为了降低空间复杂度，我们可以不建出整棵线段树的结构，而是在最初只建立一个根节点，代表整个区间，当需要访问线段树的某棵子树（某个子区间）时，再建立代表这个子区间的节点。采用这种方法维护的线段树称为动态开点的线段树。
• 动态开点的线段树抛弃了完全二叉树父子节点的2倍编号规则，改为使用变量记录左右子节点的编号。同时，它也不再保存每个节点代表的区间，而是在每次递归访问的过程中作为参数传递。
• 可持久化线段树是一种静态数据结构，如果需要动态修改，需要用树状数组套可持久化线段树。

建树

动态开点建树即可。

void Build(int &o,int l,int r) {
	o=++ind;
	sum[o]=0;
	if(l==r) {
		return;
	}
	Build(ls[o],l,mid);
	Build(rs[o],mid+1,r);
	return;
}

插入

左右子节点继承上一版本即可，注意$sum$应当较上一版本$+1$。

void Update(int &o,int l,int r,int pre,int x) {
	o=++ind;
	ls[o]=ls[pre],rs[o]=rs[pre],sum[o]=sum[pre]+1;
	if(l==r) {
		return;
	}
	if(x<=mid) {
		Update(ls[o],l,mid,ls[pre],x);
	}
	else {
		Update(rs[o],mid+1,r,rs[pre],x);
	}
}

查询静态区间第k小的数

注意是用右边界的左子节点减去左边界的左子节点。

int Kth(int l,int r,int x,int y,int k) {
	if(l==r) {
		return l;
	}
	int tmp=sum[ls[y]]-sum[ls[x]];
	if(k<=tmp) {
		return Kth(l,mid,ls[x],ls[y],k);
	}
	else {
		return Kth(mid+1,r,rs[x],rs[y],k-tmp);
	}
}

板子

板子我是用$namespace$写的，放在这方便以后用。
注意线段树的数组开40倍。

#define N 200010
#define mid ((l+r)>>1)

int n,m,siz,ind;
int rt[(N<<5)+(N<<3)],ls[(N<<5)+(N<<3)],rs[(N<<5)+(N<<3)],sum[(N<<5)+(N<<3)],a[N],b[N];

namespace Persistence_Segment_Tree {
	void Read() {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		return;
	}
	
	void Build(int &o,int l,int r) {
		o=++ind;
		sum[o]=0;
		if(l==r) {
			return;
		}
		Build(ls[o],l,mid);
		Build(rs[o],mid+1,r);
		return;
	}
	
	void Update(int &o,int l,int r,int pre,int x) {
		o=++ind;
		ls[o]=ls[pre],rs[o]=rs[pre],sum[o]=sum[pre]+1;
		if(l==r) {
			return;
		}
		if(x<=mid) {
			Update(ls[o],l,mid,ls[pre],x);
		}
		else {
			Update(rs[o],mid+1,r,rs[pre],x);
		}
	}
	
	void Init() {
		std::sort(b+1,b+n+1);
		siz=std::unique(b+1,b+n+1)-b-1;
		Build(rt[0],1,siz);
		for(int i=1;i<=n;i++) {
			int val=std::lower_bound(b+1,b+siz+1,a[i])-b;
			Update(rt[i],1,siz,rt[i-1],val);
		}
	}
	
	int Kth(int l,int r,int x,int y,int k) {
		if(l==r) {
			return l;
		}
		int tmp=sum[ls[y]]-sum[ls[x]];
		if(k<=tmp) {
			return Kth(l,mid,ls[x],ls[y],k);
		}
		else {
			return Kth(mid+1,r,rs[x],rs[y],k-tmp);
		}
	}
	
	void Solve() {
		for(int i=1;i<=m;i++) {
			int l,r,k,ans;
			scanf("%d%d%d",&l,&r,&k);
			ans=b[Kth(1,siz,rt[l-1],rt[r],k)];
			printf("%d
",ans);
		}
		return;
	}
}