为啥叫主席树？

很多人一看到这名字觉得这肯定是个很厉害的数据结构，从而望而却步。
其实为啥这个数据结构叫主席树呢，emmmm…

这个数据结构是这位同学在考场上想出来的，而他的名字与某位主席缩写有一致的相似性QAQ

引入题（静态区间第k小)

题目描述

如题，给定 n n n 个整数构成的序列，将对于指定的闭区间查询其区间内的第 k k k 小值。

输入格式

第一行包含两个正整数 n , m n,m n,m，分别表示序列的长度和查询的个数。

第二行包含 n n n 个整数，表示这个序列各项的数字。

接下来 m m m 行每行包含三个整数 l , r , k l, r, k l,r,k , 表示查询区间 [ l , r ] [l, r] [l,r] 内的第 k k k 小值。

输出格式

输出包含 k k k 行，每行一个整数，依次表示每一次查询的结果

输入输出样例
输入 #1

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出 #1

6405
15770
26287
25957
26287

想想怎么解决这题

唔好像只会暴力

如果简化一下

先假设每个数值域都在 [ 1 , n ] [1,n] [1,n]
假如每次询问都是问 [ 1 , n ] [1,n] [1,n] 的第 k k k 大，那怎么做呢？（雾似乎直接排序然后输出就好了
但如果我们硬要用数据结构来动态查询呢？我们学过啥？
权值线段树！！！
权值线段树的每个叶子节点代表的是一个数，节点的值是这个数出现的次数。
那么我们每次查找 [ 1 , n ] [1,n] [1,n] 中的第 k k k 大，查询的时候判断一下 k k k 和 s u m [ l s o n ] sum[lson] sum[lson] 的大小，如果 k k k 小，说明 [ l , m ] [l,m] [l,m] 范围内已经有了不止 k k k 个数，说明第 k k k 大肯定在左子树内，于是就往左子树查询第 k k k 大数，否则就往右子树查询第 k − s u m [ l s o n ] k - sum[lson] k−sum[lson] 大的数。

问题来了

现在求的不是区间 [ 1 , n ] [1,n] [1,n]，而是区间 [ l , r ] [l,r] [l,r]，这怎么破呢？
要是我们能够在 [ l , r ] [l,r] [l,r] 之间建一棵权值线段树就好了QAQ
没错这就是主席树的思想！
为了得到区间 [ l , r ] [l,r] [l,r] 的权值线段树！
如果我们得到了 [ 1 , r ] [1,r] [1,r] 和 [ 1 , l − 1 ] [1,l-1] [1,l−1] 的权值线段树，那么求 [ l , r ] [l,r] [l,r] 每个节点的 s u m sum sum 值不就是 s u m [ r t ] − s u m [ l a s ] sum[rt] - sum[las] sum[rt]−sum[las] 了吗！！！
（ r t rt rt 指 [ 1 , r ] [1,r] [1,r] 的权值线段树的当前节点， l a s las las 指 [ 1 , l − 1 ] [1,l-1] [1,l−1] 的权值线段树的当前节点

进入正题（敲黑板

考虑建立 [ 1 , i ] [1,i] [1,i] 的权值线段树

如果我们每次都直接建树，时空复杂度还是爆炸
问题在于我们每次都要重新建立 [ 1 , i − 1 ] [1,i-1] [1,i−1] 的信息
如果这部分信息能直接利用起来就好了！
事实上真的可以直接用！！
接着往下看！

建树


这个图是 [ 1 , i ] [1,i] [1,i] 的权值线段树，可以看到，每颗权值线段树，都和前一棵有很强的相似性！！！其实，每一棵和前一棵的区别仅仅在于一条链上！
每次对 [ 1 , i ] [1,i] [1,i] 建树，插入 a [ i ] a[i] a[i] 这个节点时，最多只会影响到 l o g n logn logn 个节点的 s u m sum sum 值 (单点插入的复杂度是 l o g n logn logn)，我们其实只要建这 l o g n logn logn 个节点就好了！其他节点直接用 i − 1 i-1 i−1 那棵树的，就可以避免重复建树！
先看看 u p d a t e update update 部分的代码

void update(int l, int r, int &rt, int p, int las){
	rt = ++cnt;
	sum[rt] = sum[las] + 1;
	lch[rt] = lch[las];
	rch[rt] = rch[las];
	if(l == r) return;
	int m = l + r >> 1;
	if(p <= m) update(lson, p, lch[las]);
	else update(rson, p, rch[las]);
}

这里我们用的是动态开点，也就是对于每一个和前一棵树不同的点，都对它单独开一个新的空间。
很容易发现，我们每次 u p d a t e update update，都会开 l o g n logn logn 个空间，所以主席树的空间复杂度是 n l o g n nlogn nlogn 的

查询

查询部分的原理就是权值线段树！上面已经说过了！
直接看代码！

int find(int l, int r, int rt, int k, int las){
	if(l == r) return l;
	int s = sum[lch[rt]] - sum[lch[las]], m = l + r >> 1;
	if(k <= s) return find(lson, k, lch[las]);
	return find(rson, k - s, rch[las]);
}

s u m [ r t ] − s u m [ l a s ] sum[rt] - sum[las] sum[rt]−sum[las] 就是 [ l , r ] [l,r] [l,r] 的权值线段树的节点的 s u m sum sum 值！
如果你理解了上面的部分，这里应该很好理解！

最后补充一下主席树一般用到的一些东西

离散化

在一般的题目中，数据范围一般不是 [ 1 , n ] [1,n] [1,n]，而是 i n t int int 范围，于是我们要离散化，把数据映射到 [ 1 , n ] [1,n] [1,n] 范围。其实离散化就是用每个数的排名来代替这个数，要访问这个数只要在原来排序后的数组中访问下标就可以了。
也就是说，离散化后，我们用这个数的排名来代替这个数了！

离散化代码如下

	for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + i);
	m = unique(b + 1, b + n + 1) - b - 1;
	for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

u n i q u e unique unique 的作用是去重， m m m 是去重后的数组有多少个数。

总代码如下

#include <bits/stdc++.h>
#define N 200005
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
using namespace std;
int cnt, root[N], lch[N * 32], rch[N * 32], sum[N * 32], a[N], b[N];
void build(int l, int r, int &rt){
	rt = ++cnt;
	if(l == r) return;
	int m = l + r >> 1;
	build(lson);
	build(rson);
}
void update(int l, int r, int &rt, int p, int las){
	rt = ++cnt;
	sum[rt] = sum[las] + 1;
	lch[rt] = lch[las];
	rch[rt] = rch[las];
	if(l == r) return;
	int m = l + r >> 1;
	if(p <= m) update(lson, p, lch[las]);
	else update(rson, p, rch[las]);
}
int find(int l, int r, int rt, int k, int las){
	if(l == r) return l;
	int s = sum[lch[rt]] - sum[lch[las]], m = l + r >> 1;
	if(k <= s) return find(lson, k, lch[las]);
	return find(rson, k - s, rch[las]);
}
int main(){
	int i, j, n, m, l, r, k, T, q;
	//scanf("%d", &T);
	T = 1;
	while(T--){
		scanf("%d%d", &n, &q);
		memset(root, 0, sizeof(root));
		memset(lch, 0, sizeof(lch));
		memset(rch, 0, sizeof(rch));
		memset(sum, 0, sizeof(sum));
		cnt = 0;
		for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
		sort(b + 1, b + i);
		m = unique(b + 1, b + n + 1) - b - 1;
		for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
		build(1, m, root[0]);
		for(i = 1; i <= n; i++) update(1, m, root[i], a[i], root[i - 1]);
		for(i = 1; i <= q; i++){
			scanf("%d%d%d", &l, &r, &k);
			j = find(1, m, root[r], k, root[l - 1]);
			printf("%d\n", b[j]);
		}
	}
	return 0;
}

总结

主席树其实就是区间的权值线段树。
任何权值线段树能支持的查询操作主席树都能有
主席树时空复杂度都是 O ( n l o g n ) O(nlogn) O(nlogn)

完结撒花！！！