可持久化线段树【主席树】详解_黄嘉泰线段树

首先科普下为什么叫主席树呢，这是因为主席树的创始人是一位叫做黄嘉泰的大佬，然后这位大佬名字的缩写是HJT，和某位伟人的名字缩写一样....haha，所以就有了主席树这个说法啦。

其实网上已经有很多博主写了关于主席树详解的博客了，但是我自己为什么还要手敲这样一份主席树教学呢？因为我在刚学主席树的时候，也是看了很多博主写的入门教程，但是没有任何单独一份就能让我搞明白什么是主席树，让我吃了很多苦头，所以我这个小博主决定自己花点时间来敲这么一份主席树的入门教学，希望对新学的你有所帮助。

 

主席树：

查询区间第K大的值。

（先要对线段树有一定了解哦）

 

首先在讲主席树之前，要科普一下离散化这个小知识。

我们设想一下如果让你建一颗线段树，储存1-4的值，那么你要开多大的数组？首先我们肯定要有一个根节点存储1-4的信息，然后根节点的左右子树分别存1-2和3-4的信息，最后还有4个单点值的信息，一共2^3-1=7个数组，那我要储存1-8的值呢，童鞋们可以自己手动画一下，就需要2^4-1=15个数组。那现在我给你5个数，1，5，100，666000，99990000，你要怎么帮我存到线段树中呢？要开多大的数组呢？这样无疑非常的浪费空间，以为建了很多不需要的子树，那如何去避免？这就要用到我们的离散化思想了哦。

 

现在来讲一下什么是离散化，平常做题的过程中你会发现有些问题可能需要我们把数据本身大小当作数组的下标来存储一些信息，例如桶排序等，这个时候我给出了5个数给你，1，5，100，666000，99990000，很显然，数组不可能开到99990000这么大，那咋整呢？这个时候离散化的思想就出来咯，这种题目往往我们只关心的是哪个数相较与哪个数大还是小，666000是比99990000小的，但是又比100要大，离散化的思想就是通过改变数本身的大小，但是不改变它们之间的大小关系，也就是说：

1<5<100<666000<99990000其实是等价于1<2<3<4<5，他们之间的大小关系是没有发生改变的，但是通过离散化，我们就能把这5个数的信息都存到数组里，特别是创建一棵树去储存的时候，节省了空间，降低了空间复杂度。

做主席树题目的时候，我们常常会用到三个c++函数：unique，erase和lower_bound。

首先我们来介绍一下unique函数，我们创建一个数组，放进了5个值1，1，2，2，3，调用unique函数，把a数组的起始地址和结尾地址传了进去，unique就会帮我们把这个序列中相邻的重复元素移到数组的末尾，并且最终返回的是没有重复元素的序列中最后一个元素的地址，也就是说当我们用返回的值减去a的起始地址，我们就能得到没有重复元素的数组大小，像1，1，2，2，3，就会返回3，并且a数组前面3个数为1，2，3。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[5]={1,1,2,2,3};
	for(int i=0;i<5;i++){
		printf("%d ",a[i]);
	}
	printf("\n\n");
    int size = unique(a,a+5)-a;
    printf("size = %d\n\n",size);
  
	for(int i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}

运行结果：
 
1 1 2 2 3
 
size=3
 
1 2 3

然后erase函数是传进两个地址，删除容器中两个地址间的元素，例如vector数组我放进了3个数：1，2，3。然后我调用erase函数，传进了vector.begin()+1,vector.end()这两个地址，那么vector的大小就会变成1，里面只存放了数3，1和2都被删除了。

#include <bits/stdc++.h>
using namespace std;
int main(){
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	for(int i=0;i<v.size();i++){
		printf("%d ",v[i]);
	}
	printf("\n");
	v.erase(v.begin()+1,v.end());
	for(int i=0;i<v.size();i++){
		printf("%d ",v[i]);
	}
	printf("\n");
}

运行结果：
1 2 3
1

lower_bound传进去三个值，一个是起始地址，一个是结尾地址，最后一个是一个数num，然后返回第一个大于等于num的地址，如果没有就返回end()地址。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[5]={1,2,3,4,5};
	int index = lower_bound(a,a+5,1)-a;//结尾地址-起始地址=下标 
	printf("%d\n",index);
	index = lower_bound(a,a+5,6)-a;
	printf("%d\n",index);
}

运行结果：
0
5

嘤嘤嘤，小知识都讲的差不多了，咱们可以开始进入正题了，来讲讲什么是主席树。

来，现在给你一道题，现在给出一个n，然后输入n个数，一共m次询问，每次询问区间[left,right]中的第k大的数。

最暴力的方法就是把left到right的区间进行一次从小到大的排序，然后输出第k个，所需的时间复杂度是O(mnlogn)，但是这种方法肯定会TLE（超时）啦，不然我还讲啥主席树。。。

这种区间的问题，我们自然而然的就会想到使用线段树了，但是细想一下，如果我现在要把3，5，1，2，6，4这6个数放进线段树中，然后查询区间[2，3](假设下标从1开始)中第二大的值，我们要怎么去操作？如果我们问的是在整个区间范围，是可以在线段树中找到第二大的值，但是如果局限在某一个区间，我们是不能确定的，为什么？虽然我们的确存了数据进入了线段树中，但是到底哪一个数是在先放进来，哪一个数后放进来，线段树是没有保存这个信息的。也就是说[2,3]区间里有什么数，线段树是不知道的，也就不能找到第k大的数到底是哪一个。所以主席树就诞生啦，主席树也叫做可持久化线段树，顾名思义，它是可以保存每次进行insert操作的记录，每次新插入一个值，就会产生一个新的版本。

按照我这样说的，最暴力的方法其实就相当于建了n个线段树数组，然后每次新插入一个数就相当于重新建了一个线段树，每个线段树是一个新的版本。例如我现在要进行4次操作，分别insert：1，3，4，2这四个数字。

这样的创建方法虽然很直观能看出每次的操作，但是每次新插入一个数都要重新建一颗线段树，并且要把之前的历史版本都导入到新的线段树中，空间复杂度和时间复杂度都是不允许的。通过观察我们发现，当我们insert完1后，去insert3时，我们版本号为2的导入先前的历史版本号1中左子树[1,2]区间是没有进行insert操作的，因为我要进行的是右子树[3,4]区间的插入，所以导致了左子树[1,2]区间及其树下的这部分空间是重复的，也就是浪费了空间和时间去重新copy了一下。既然左子树[1,2]区间是没有改变的，那我们就可以在新的版本树中让根节点root的左节点直接指向上一个版本的左子树，这样就节省了空间，也节省了时间，我们只需要把要进行插入所经过的节点依次建一遍就可以了（如下图蓝色框即），也就是每次进行插入操作只需要新建logn个节点就可以了。

 

像上图我们第二版本树的左节点直接连接到历史版本树的左子树上，构成了一颗新的树，这就是成了一种可以支持历史询问的数据结构，也就是主席树啦。我们在每次查询[left，right]区间的时候，首先我们先不管它如何实现，我们现在要查询[left，right]区间的数据，那么第right版本树记录了从第一次到第right次插入的数据，而第left-1版本树记录了从第一次到left-1次插入的数据，那么从数学的角度，我们让第right版本树减去第left-1版本树得到的就是left到right区间的数据，既然我们已经得出了left到right区间的数据了，那么我们就能进行查询第k大的操作了。

我们在每次插入的过程中，都会把每个区间的sum++（该区间操作的次数），这样每次访问左子树和右子树的时候，都能知道该区间下有多少个数，假设现在我要找第k=5大的数，左子树有3个数，右子树有5个数，那么就递归往右子树找第k大的值，因为右子树存放的值会比较大，而且存在5个，里面最小的一个就是我们要找的值；再比如我要找的是第k=6大的数，那么就要递归往左子树找第k-5个大的数，因为右子树已经存在5个比左子树要大的数，所以左子树第k-5=1大数就是我们要找的数。这样递归到最后，就能求出[left，right]区间第k大的值。

现在，一起来实际操作一下吧！

原题网址：https://www.luogu.org/problem/P3834

P3834 【模板】可持久化线段树 1（主席树）

提交 21.16k

通过 9.96k

时间限制 1.00s ~ 1.20s

内存限制 125.00MB ~ 250.00MB

题目背景

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #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

说明/提示

数据范围：

对于20%的数据满足：1≤N,M≤101 \leq N, M \leq 101≤N,M≤10

对于50%的数据满足：1≤N,M≤1031 \leq N, M \leq 10^31≤N,M≤103

对于80%的数据满足：1≤N,M≤1051 \leq N, M \leq 10^51≤N,M≤105

对于100%的数据满足：1≤N,M≤2⋅1051 \leq N, M \leq 2\cdot 10^51≤N,M≤2⋅105

对于数列中的所有数aia_iai​，均满足−109≤ai≤109-{10}^9 \leq a_i \leq {10}^9−109≤ai​≤109

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为[25957,6405,15770,26287,26465][25957, 6405, 15770, 26287, 26465 ][25957,6405,15770,26287,26465]

第一次查询为[2,2][2, 2][2,2]区间内的第一小值，即为6405

第二次查询为[3,4][3, 4][3,4]区间内的第一小值，即为15770

第三次查询为[4,5][4, 5][4,5]区间内的第一小值，即为26287

第四次查询为[1,2][1, 2][1,2]区间内的第二小值，即为25957

第五次查询为[4,4][4, 4][4,4]区间内的第一小值，即为26287

附上AC代码：（光说没用，接下来的路就要自己去走了，花时间去理解下面这份模板题代码，写了很多注释，祝好运！）

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5+5;
vector<int>v;
struct knight{//left，right记录左右节点，sum记录了当前树下进行过几次操作（存在几组数据） 
	int left;
	int right;
	int sum;
}hjt[MAXN * 40];
int cnt;
int a[MAXN],root[MAXN];
int getid(int x){//离散化，通过lower_bound来返回当前值的下标+1 
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
 
//这里注意now是用的&now，这样递归更改后是会改变新版本树的，而历史版本树我们是不需要更改，所以不用 
void insert(int left,int right,int pre,int &now,int value){
	hjt[++cnt] = hjt[pre];//每次递归进来，历史版本树都会把左右子树所在的位置赋值给新版本树 
	now = cnt;
	hjt[now].sum++;//进行插入操作，总记录+1 
	
	if(left==right)//递归退出条件，到了树的枝叶边缘 
		return;
	int mid = left+right>>1;
	/*
	要更新的插入操作就会去创建新的左或右子树 
	*/ 
	if(value<=mid){
		insert(left,mid,hjt[pre].left,hjt[now].left,value);
	}else{
		insert(mid+1,right,hjt[pre].right,hjt[now].right,value);
	}
}
 
int query(int left,int right,int L,int R,int k){
	if(left==right)
		return left;
	int mid = left+right>>1;
	int tep = hjt[hjt[R].left].sum-hjt[hjt[L].left].sum;//判断当前子树所存在数的个数，判断往哪一个子树寻找 
	if(k<=tep){
		return query(left,mid,hjt[L].left,hjt[R].left,k);//如果个数大于要寻找的k，我们就往左子树第k小的数 
	}else{
		return query(mid+1,right,hjt[L].right,hjt[R].right,k-tep);//否则往右子树，寻找第k-tep个小的数 
	}
}
 
 
int main(){
	int n,m;
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			cin>>a[i];
			v.push_back(a[i]);//我们把每个数都放进vector中 
		}
		sort(v.begin(),v.end());//从小到大排序 
		v.erase(unique(v.begin(),v.end()),v.end());//去重并且删除掉 
		/*
		真正保存了数据的是a数组，我们用vector存进去是为了去离散化数据，所以我们只需要知道里面有几个值就可以了 
		*/ 
		for(int i=1;i<=n;i++){
			insert(1,n,root[i-1],root[i],getid(a[i])); 
			/*
			root[i]是新的版本树 
			root[i-1]是上一个历史版本树 
			getid这个函数就是离散化，我们把每个数据都用下标+1（从1开始）当作这个数的大小，但是没有改变它们之间的大小关系
			这样数据与离散化后的数就有了联系			
			*/ 
		}
		int x,y,k;
		for(int i=0;i<m;i++){
			cin>>x>>y>>k;
			cout<<v[query(1,n,root[x-1],root[y],k)-1]<<endl;
			/*
				像我们之前说的，只需要用第right版本树-第left-1版本树就可以啦，
				query函数返回的是下标，我们进行-1操作，就能对应到vector中存进去的真实数据了 
			*/
		}
	}
}

如果熟悉了上面的代码，自己也尝试编写过了，可以来看一份时间复杂度更低一点的代码，也是这道模板题滴：

#include <iostream>
#include <algorithm>
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 2e5+5;
int root[maxn],sum[maxn<<5],R[maxn<<5],L[maxn<<5];
int cnt;
int a[maxn],b[maxn];
int build(int left,int right){
	int rt = ++cnt;
	sum[rt] = 0;
	int mid = left+right>>1;
	if(left<right){
		L[rt] = build(left,mid);
		R[rt] = build(mid+1,right);
	}	
	return rt;
}
int update(int left,int right,int pre,int value){
	int rt = ++cnt;
	sum[rt] = sum[pre]+1;
	L[rt] = L[pre];
	R[rt] = R[pre];
	int mid = left+right>>1;
	if(left<right){
		if(value<=mid){
			L[rt] = update(left,mid,L[pre],value);
		}else{
			R[rt] = update(mid+1,right,R[pre],value);
		}
	}
	return rt;
}
int query(int left,int right,int x,int y,int k){
	if(left==right)
		return left;
	int mid = left+right>>1;
	int temp = sum[L[y]]-sum[L[x]];
	if(temp>=k){
		return query(left,mid,L[x],L[y],k);
	}else{
		return query(mid+1,right,R[x],R[y],k-temp);
	}
}
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+1+n);
		int nn = unique(b+1,b+1+n)-b-1;
		root[0] = build(1,nn);
		for(int i=1;i<=n;i++){
			int value = lower_bound(b+1,b+nn+1,a[i])-b; 
			root[i] = update(1,nn,root[i-1],value);
		}
		int x,y,k;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&x,&y,&k);
			printf("%d\n",b[query(1,nn,root[x-1],root[y],k)]);
		}
	}
}