主席树

发表于 更新于 分类于 阅读次数： Changyan：

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

对于原序列的每一个前缀[1…i]建立出一颗线段树维护值域，建立一棵线段树维护值域上每个数出现的次数，则其树是可减的

​ —-黄嘉泰

如果对线段树不了解的，请学习前置技能：线段树]

值域线段树

对一个值域上的个数进行维护的线段树

举个例子:1,1,2,3,3,3,4,其值域 线段树为：

主席树

hjt树便是基于权值线段树的基础而建立的

经典例题：求区间上的第k大树

步骤1.先对数据进行离散化（此步骤不是重点，因此省略）

步骤2：如何处理区间[L,R]这个条件呢？在考虑右侧 ,R] 这个限定的时候，我们只需要寻找第R个版本即可。

那么，怎么处理 [L, 这个限定呢？

这也是这道题目最关键的：我们在对第R个版本进行递归的查找的时候，我们会先搜左子树，如果k大于左子树的数量我们才会在右子树上搜索。那么左子树的数量就显得尤为关键了。

回顾hjt那句话，因为主席树维护的是权值线段树，所以我们在递归第R个版本的时候，实际上是递归的除去第L-1个版本的所有内容，因此我们只需利用权值线段树的性质，减去L-1版本的内容就好啦👲

下面是算法拆分：

树的存储

1
2
3
4
5
6
//使用结构体存储主席树，其中l，r分别表示指向左右儿子的指针
struct Node{
    int l,r;
    int cnt;  //对应权值线段树的值域内的个数
}tr[M*40];
int root[M],idx;  //the root pool&point

建树

1
2
3
4
5
6
7
8
9
//build()建树
int build(int pre,int l,int r){
    int now=++idx;
    if(l==r)  return now;
    int mid=l+r>>1;
    tr[now].l=build(tr[pre].l,l,mid);
    tr[now].r=build(tr[pre].r,mid+1,r);
    return now;
}

树的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//insert into thr tree
int insert(int pre,int l,int r,int x){
    int now=++idx;  //主席树常规流程，先获取分配的内存
    tr[now]=tr[pre];  //前一版的复刻
    if(l==r){
   		tr[u].cnt++;
        return now;
    }
    int mid=l+r>>1;
    if(x<=mid) tr[u].l=insert(tr[pre].l,l,mid,x);  
    else if(x>mid) tr[u].r=insert(tr[pre].r,mid+1,r,x);
    tr[now].cnt=tr[tr[now].l].cnt+tr[tr[now].r].cnt;
    return now;
}

//__main__:
root[i]=insert(root[i-1],1,n,w[i]);

树的查询

1
2
3
4
5
6
7
8
//find the kth num in the segment of [l,r]
int query(int pre,int now,int l,int r,int k){
    if(l==r) return r;
    int cnt=tr[tr[now].l].cnt-tr[tr[pre].l].cnt; //cnt in [l,~
    int mid=l+r>>1;
    if(k<=cnt) return query(tr[pre].l,tr[now].l,l,mid,k);
    else return query(tr[pre].r,tr[now].r,mid+1,r,k-cnt);
}

板子题：洛谷P3834 https://www.luogu.com.cn/problem/P3834

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#define N 200010
using namespace std; 

//read(x)
template <typename T>void read(T &x){x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}x*=f;return;}
//write(x)
template <typename T>void write(T x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');return;}      

struct Node{
	int l,r;  //left tree point&righht tree point
	int cnt;	
}tr[N*30];
int root[N],idx=0;
int a[N];
vector<int> alls;
int n,m;

int get_id(int x){return lower_bound(alls.begin(),alls.end(),x)-alls.begin();}

int build(int l,int r){
	int now=++idx;
	if(l==r) return now;
	int mid=l+r>>1;
	tr[now].l=build(l,mid),tr[now].r=build(mid+1,r);
	return now;
}

int insert(int pre,int l,int r,int x){
	int now=++idx;
	tr[now]=tr[pre]; //paste previos
	if(l==r){
		tr[now].cnt++;
		return now;
	}
	int mid=l+r>>1;
	if(x<=mid) tr[now].l=insert(tr[pre].l,l,mid,x);
	else tr[now].r=insert(tr[pre].r,mid+1,r,x);
	tr[now].cnt=tr[tr[now].l].cnt+tr[tr[now].r].cnt;
	return now;
}

int query(int now,int pre,int l,int r,int k){
	if(l==r) return r;
	int cnt=tr[tr[now].l].cnt-tr[tr[pre].l].cnt;
	int mid=l+r>>1;
	if(k<=cnt) return query(tr[now].l,tr[pre].l,l,mid,k);
	else return query(tr[now].r,tr[pre].r,mid+1,r,k-cnt); //k should minus cnt of left
}

int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
		alls.push_back(a[i]);
	}
	sort(alls.begin(),alls.end());
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	
	root[0]=build(0,alls.size()-1);
	
	for(int i=1;i<=n;i++)
		root[i]=insert(root[i-1],0,alls.size()-1,get_id(a[i]));
	
	for(int i=1;i<=m;i++){
		int l,r,k;
		read(l),read(r),read(k);
		write(alls[query(root[r],root[l-1],0,alls.size()-1,k)]);
		puts("");
	}
	return 0;
}

主席树维护普通线段树：可持久化数组

可持久化数组是用主席树维护普通线段树，是学习可持久化并查集的基础

  • 可持久化数组支持历史版本的单点修改和单点查询

下面是整个算法的步骤：

  • 结构
1
2
3
4
struct Node{
    int l,r,v;
} tr[M*30~40]; //开30到40倍数据
int root[M],int w[M],idx=0; //分别存储根节点，原数组，内存分配指针
  • 建树
1
2
3
4
5
6
7
8
9
10
11
void build(int &now,int l,int r){
    now=++idx;  //万古不变，为当前节点申请内存
    if(l==r){
        tr[now].v=w[r]; //更新叶子节点信息
        return ;
    }
    int mid=l+r>>1;
    build(tr[now].l,l,mid),build(tr[now].r,mid+1,r);
}
//__main__:
build(root[0],l,r);
  • 更新节点
1
2
3
4
5
6
7
8
9
10
11
void modify(int l,int r,int &now,int pre,int pos,int x){ //搜索[l,r],依据pre版本对now版本找到pos位置修改成x
	now=++idx;	//申请内存
    tr[now]=tr[pre]; 	//复制一份之前版本的复刻
    if(l==r){
        tr[now].v=x;
        return ;
    }
    int mid=l+r>>1;  //这里就是不断缩小区间知道找到pos所在的区间
    if(pos<=mid) modify(l,mid,tr[now].l,tr[pre].l,int x);
    else modify(mid+1,r,tr[now].r,tr[pre].r,int x);
}
  • 查询
1
2
3
4
5
6
int query(int l,int r,int now,int pos){
    if(l==r) return tr[now].v; //说明搜索到了叶子节点，直接返回当前节点的值
    int mid=l+r>>1;
    if(pos<=mid) return query(l,mid,tr[now].l,pos);
    else return query(mid+1,r,tr[now].r,pos);
}

板子题：洛谷P3919 https://www.luogu.com.cn/problem/P3919

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#define M 1000010
using namespace std; 

//read(x)
template <typename T>void read(T &x){x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}x*=f;return;}
//write(x)
template <typename T>void write(T x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');return;}      

struct Node{
	int l,r;
	int v;
} tr[M*20];
int root[M],idx=0;
int n,m,w[M];

void build(int &u,int l,int r){
	u=++idx;
	if(l==r){
		tr[u].v=w[r];
		return ;
	}
	int mid=(l+r)>>1;
	build(tr[u].l,l,mid),build(tr[u].r,mid+1,r);
}

void modify(int l,int r,int pre,int &now,int pos,int x){
	now=++idx;  //new一块空间
	tr[now]=tr[pre]; //复制上一个版本
	if(l==r){
		tr[now].v=x;  //修改此处
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid) modify(l,mid,tr[pre].l,tr[now].l,pos,x);
	else modify(mid+1,r,tr[pre].r,tr[now].r,pos,x);		
}

int query(int l,int r,int now,int pos){
	if(l==r) return tr[now].v;
	int mid=l+r>>1;
	if(pos<=mid) return query(l,mid,tr[now].l,pos);
	else return query(mid+1,r,tr[now].r,pos);
}

int main(){
	read(n),read(m);
	
	for(int i=1;i<=n;i++)
		read(w[i]);
		
	build(root[0],1,n);	
	
	for(int i=1;i<=m;i++){
		int pre,op,pos,x; 
		//pre版本，op操作，p位置，修改x
		read(pre),read(op),read(pos);
		if(op==1){
			read(x);
			modify(1,n,root[pre],root[i],pos,x);
		}
		else{
			write(query(1,n,root[pre],pos));
			puts("");
			root[i]=root[pre];
		}
	}
	return 0;
}