主席树详解——区间的权值线段树

为啥叫主席树？

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

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

---

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

题目描述

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

输入格式

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

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

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

问题来了

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

---

进入正题（敲黑板

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

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

建树

这个图是 $[1,i]$[1,i] 的权值线段树，可以看到，每颗权值线段树，都和前一棵有很强的相似性！！！其实，每一棵和前一棵的区别仅仅在于一条链上！
每次对 $[1,i]$[1,i] 建树，插入 $a[i]$a[i] 这个节点时，最多只会影响到 $logn$logn 个节点的 $sum$sum 值 (单点插入的复杂度是 $logn$logn)，我们其实只要建这 $logn$logn 个节点就好了！其他节点直接用 $i-1$i−1 那棵树的，就可以避免重复建树！
先看看 $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]);
}

这里我们用的是动态开点，也就是对于每一个和前一棵树不同的点，都对它单独开一个新的空间。
很容易发现，我们每次 $update$update，都会开 $logn$logn 个空间，所以主席树的空间复杂度是 $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]);
}

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

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

离散化

在一般的题目中，数据范围一般不是 $[1,n]$[1,n]，而是 $int$int 范围，于是我们要离散化，把数据映射到 $[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;

$unique$unique 的作用是去重，$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(nlogn)$O(nlogn)

完结撒花！！！