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

发表于 | 分类于 | | 浏览量： 次

骚年，你需要一棵主席树！它会赐予你力量！

传送门

洛谷的主席树模板题

正文

引入问题

我们可能时常会遇到这样的一类问题：给定一个序列$A$和若干组询问，每次给定一个区间$[L,R]$和一个参数$k$，问序列上该区间中第$k$大的元素是多少。

对于这类问题，暴力算法显而易见(但是会T飞)。一个很好的解决办法就是用主席树(其实洛谷上的这道模板题不强制在线，分块+莫队可以AC，还跑得贼快)。

说一句题外话，主席树这种数据结构据说是一位名字缩写是HJT的神仙在考场上现场yy出来的，而HJT正是新中国历史上一位著名主席的名字缩写，因此得名。

考虑初始版本

首先请确保你已经掌握普通线段树的写法，不会的童鞋请自行Ctrl+W。

我们建$n$权值棵线段树，第$i$棵线段树需要维护序列$A_1$~$A_i$中，每个权值出现的次数。比如说第$i$棵线段树上的一个节点管辖的权值区间是$[S,T]$，该节点需要储存满足$A_j\inS,T$的元素$A_j$的个数。可以将这些线段树一开始就构造好。

当进行询问的时候，如果当前的询问区间是$[L,R]$那么我们就把第$L-1$棵线段树和第$R$棵线段树拎出来，根据容斥的原理，将两棵线段树每个节点的权值相减就能得到一颗有我们想要用的包含$A_L$~$A_R$的信息的权值线段树。

然后我们就在这棵线段树上计算答案。

首先先遍历树根，假设当前节点管辖的权值区间是$[L,R]$，权值在该区间内的元素的个数和是$sum$。

如果$sum\leq k$，那么遍历当前节点的左儿子。

否则将$k$的值减去$sum$，然后遍历右儿子。

循环以上步骤，直到$L=R$，此时的$L$就是答案。

完善初始版本

说真的，初始版本又难码又慢，比暴力算法还垃圾QwQ

现在考虑完善一下初始版本，让它成为一棵真正的主席树！

首先在询问的时候，不需要每次都重构一棵线段树，用两个指针同时在两棵线段树上遍历，查个数的时候再相减就行了。

其次，如果真的开$n$棵完整的权值线段树，内存不炸才怪QwQ。

我们发现，第$i$棵权值线段树是在继承第$i-1$棵的信息的基础上，再添加第$i$个元素的信息。而根据线段树的性质，每进行一次修改，最多只会改变$\log n$个节点的信息。所以我们动态开点，在开第$i$棵线段树时，只新开修改过的节点，并把新开的节点直接接到没有修改过的已有节点上就可以了QwQ。骚年，你感受到了可持久化的力量了吗？

还有，由于元素的权值可能很大，我们需要将原序列先离散化。

这样，我们就成功地把时间复杂度和空间复杂度都下压至$\Theta(n\log n)$的水平。主席树万岁！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200005,LOG=20;
int n,m,cnt,A[maxn],B[maxn];map<int,int> H;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct ChairmanTree                  //封装大法好
{
	int tot,T[maxn];
	struct Node{int L,R,Sum;}Tree[maxn*LOG];
	int Build(int L,int R)           //在开始添加信息之前，先初始化
	{
		int rt=++tot,mid=L+R>>1;
		if(L>=R) return rt;
		Tree[rt].L=Build(L,mid);
		Tree[rt].R=Build(mid+1,R);
		if(rt==1) T[0]=rt;
		return rt;
	}
	int Update(int num,int pre,int L,int R)  //添加信息
	{
		int rt=++tot,mid=L+R>>1;
		Tree[rt].L=Tree[pre].L;Tree[rt].R=Tree[pre].R;Tree[rt].Sum=Tree[pre].Sum+1;
		if(L>=R) return rt;
		if(num<=mid) Tree[rt].L=Update(num,Tree[pre].L,L,mid);
		else Tree[rt].R=Update(num,Tree[pre].R,mid+1,R);
		return rt;
	}
	int Query(int u,int v,int k,int L,int R)  //询问
	{
		int mid=L+R>>1,x=Tree[Tree[v].L].Sum-Tree[Tree[u].L].Sum;
		if(L==R) return mid;                  //找到了
		if(x>=k) return Query(Tree[u].L,Tree[v].L,k,L,mid); //分类讨论
		else return Query(Tree[u].R,Tree[v].R,k-x,mid+1,R);
	}
}CT;
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) A[i]=B[i]=read();
	sort(B+1,B+1+n);cnt=unique(B+1,B+1+n)-B-1;  //离散化
	for(int i=1;i<=cnt;i++) H[B[i]]=i;
	CT.Build(1,cnt);
	for(int i=1;i<=n;i++) CT.T[i]=CT.Update(H[A[i]],CT.T[i-1],1,cnt);
	while(m--)
	{
		int L=read(),R=read(),k=read();
		printf("%d\n",B[CT.Query(CT.T[L-1],CT.T[R],k,1,cnt)]);
	}
	return 0;
}

其他

其实主席树也可以维护带修改操作的序列，但是蒟蒻我现在还不会QwQ。