主席树

转自：https://www.cnblogs.com/zyf0163/p/4749042.html

主席树的每个节点对应一颗线段树，此处有点抽象。在我们的印象中，每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息（信息视具体问题定）。对于一个待处理的序列a[1]、a[2]…a[n]，有n个前缀。每个前缀可以看做一棵线段树，共有n棵线段树；若不采用可持久化结构，带来的严重后果就是会MLE，即对内存来说很难承受。根据可持久化数据结构的定义，由于相邻线段树即前缀的公共部分很多，可以充分利用，达到优化目的，同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点信息，这些可能可能出现在根节点也可能出现在叶节点。

下面是某大牛的理解：所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。

我自己对主席树的理解，是一个线段树在修改一个值的时候，它只要修改logn个节点就可以了，那么我们只要每次增加logn个节点就可以记录它原来的状态了, 即你在更新一个值的时候仅仅只是更新了一条链，其他的节点都相同，即达到共用。由于主席树每棵节点保存的是一颗线段树，维护的区间相同，结构相同，保存的信息不同，因此具有了加减性。（这是主席树关键所在，当除笔者理解了很久很久，才相通的），所以在求区间的时候，若要处区间[l, r]， 只需要处理rt[r] - rt[l-1]就可以了，（rt[l-1]处理的是[1,l-1]的数，rt[r]处理的是[1,r]的数，相减即为[l, r]这个区间里面的数。

比如说（以区间第k大为例hdu2665题目戳这里http://acm.hdu.edu.cn/showproblem.php?pid=2665）:

设n = 4，q= 1;

4个数分别为4， 1， 3 ，2;

ql = 1, qr = 3, k = 2;

1.建树

首先需要建立一棵空的线段树，也是最原始的主席树，此时主席树只含一个空节点，此时设根节点为rt[0],表示刚开始的初值状态，然后依次对原序列按某种顺序更新，即将原序列加入到对应位置。此过程与线段树一样，时间复杂度为O（nlogn)，空间复杂度O（nlog(n))（笔者目前没有完全搞清究竟是多少， 不过保守情况下，线段树不会超过4*n）

2.更新

 我们知道，更新一个叶节点只会影响根节点到该叶节点的一条路径，故只需修改该路径上的信息即可。每个主席树的节点即每棵线段树的结构完全相同，只是对应信息（可以理解为线段树的结构完全一样，只是对应叶子节点取值不同，从而有些节点的信息不同，本质是节点不同），此时可以利用历史状态，即利用相邻的上一棵线段树的信息。相邻两颗线段树只有当前待处理的元素不同，其余位置完全一样。因此，如果待处理的元素进入线段树的左子树的话，右子树是完全一样的，可以共用，即直接让当前线段树节点的右子树指向相邻的上一棵线段树的右子树；若进入右子树，情况可以类比。此过程容易推出时间复杂度为O(logn)，空间复杂度为 O(logn)。如图：

 

3.查询

先附上处理好之后的主席树， 如图:

是不是看着很晕。。。。。。笔者其实也晕了，我们把共用的节点拆开来，看下图：

啊， 这下清爽多了，一眼看下去就知道每个节点维护的是哪棵线段树了，TAT，如果早就这样写估计很快就明白了，rt[i]表示处理完前i个数之后所形成的线段树，即具有了前缀和的性质，那么rt[r] - rt[l-1]即表示处理的[l, r]区间喽。当要查询区间[1,3]的时候，我们只要将rt[3] 和 rt[0]节点相减即可得到。如图：

这样我们得到区间[l, r]的数要查询第k大便很容易了，设左节点中存的个数为cnt，当k<=cnt时，我们直接查询左儿子中第k小的数即可，如果k>cnt，我们只要去查右儿子中第k-cnt小的数即可，这边是一道很简单的线段树了。就如查找[1, 3]的第2小数（图上为了方便，重新给节点标号），从根节点1向下搜，发现左儿子2的个数为1,1<2，所有去右儿子3中搜第2-1级第1小的数，然后再往下搜，发现左儿子6便可以了，此时已经搜到底端，所以直接返回节点6维护的值3即可就可以了。

附代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N],rt[20*N],ls[N*20],re[N*20],sum[N*20];
int n,k,tot,sz,ql,qr,x,q,t;
void build(int &o,int l,int r)
{
	o=++tot;
	sum[o]=0;
	if(l==r)
	return ;
	int m=(l+r)>>1;
	build(ls[o],l,m);
	build(re[o],m+1,r);
}
void update(int &o,int l,int r,int last,int p)
{
	o=++tot;
	ls[o]=ls[last];
	re[o]=re[last];
	sum[o]=sum[last]+1;
	if(l==r)
	return ;
	int m=(l+r)>>1;
	if(p<=m)
	update(ls[o],l,m,ls[last],p);
	else
	update(re[o],m+1,r,re[last],p);
}
int query(int ss,int tt,int l,int r,int k)
{
	if(l==r)
	return l;
	int m=(l+r)>>1;
	int cnt=sum[ls[tt]]-sum[ls[ss]];          
	if(k<=cnt)
	return query(ls[ss],ls[tt],l,m,k);
	else 
	return query(re[ss],re[tt],m+1,r,k-cnt);
}
void work()
{
	scanf("%d%d%d",&ql,&qr,&x);
	int ans=query(rt[ql-1],rt[qr],1,sz,x);
	printf("%d\n",b[ans]);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
	sort(b+1,b+1+n);
	sz=unique(b+1,b+1+n)-(b+1);
	tot=0;
	build(rt[0],1,sz);
	for(int i=1;i<=n;i++)
	a[i]=lower_bound(b+1,b+1+sz,a[i])-b;
	for(int i=1;i<=n;i++)
	update(rt[i],1,sz,rt[i-1],a[i]);
	while(q--)
	work();
	}
}

4.总结

由以上可知，主席树是一种特殊的线段树集，他几乎具有所有线段树的所有优势，并且可以保存历史状态，以便以后加以利用，主席树查找和更新时时间空间复杂度均为O（logn)， 且空间复杂度约为O(nlogn + nlogn)前者为空树的空间复杂度，后者为更新n次的空间复杂度，主席树的缺点就是空间耗损巨大，但还是可以接受的。当然主席树不止这点应用，他可以处理许多区间问题，例如求区间[l, r]中的值介于[x,y]的值。总之应用多多。