主席树学习

（无详细讲解过程，因为思想很简单）

背景：

sensi:今天咱们做一下优化dp,你们看看这个简单题。
https://www.luogu.com.cn/problem/P5892
我：不会啊......
其他人：啊？这还要做？
我：......

注释：这道题需要有决策单调性思想以及前k大的主席树维护
但是我连https://www.luogu.com.cn/problem/P3834都没过欸......

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

其实就相当于修改某一个点的时候新建一个根，这个根和未修改的原点、修改后的点相连的样子
每个root都代表着一个新的版本

模板：

https://www.luogu.com.cn/problem/P3919

#include<bits/stdc++.h>
using namespace std;
int cnt=1;
vector<int>root;
struct node{
	int le,ri,ls,rs,val;
}tree[25000006];
int num[1000006];
int adddot(int x){//新加入一个点,这个点是原来x的点的变形，返回这个点的编号 
	cnt++;
	tree[cnt]=tree[x];
	return cnt;
}
void build(int rt,int l,int r){
	tree[rt].le=l;
	tree[rt].ri=r;
	if(l==r){
		tree[rt].val=num[l];
		return;
	}
	int mid=(l+r)>>1;
	tree[rt].ls=++cnt;
	tree[rt].rs=++cnt;
	build(tree[rt].ls,l,mid);
	build(tree[rt].rs,mid+1,r);
}
int change(int rt,int x,int val){
	int now=adddot(rt);
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(le==ri){
		tree[now].val=val;
		return now;
	}
	int mid =(le+ri)>>1;
	if(x<=mid){
		tree[now].ls=change(tree[rt].ls,x,val);
	}
	else{
		tree[now].rs=change(tree[rt].rs,x,val);
	}
	return now;
}
int query(int rt,int x){
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(le==ri){
		return tree[rt].val;
	}
	else{
		int mid=(le+ri)>>1;
		if(x<=mid)
			return query(tree[rt].ls,x);	//访问左子树 
		else
			return query(tree[rt].rs,x);	//访问右子树 
	}
}
int main(){
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	root.push_back(1); 
	for(int i=1;i<=n;i++){
		cin >> num[i];
	}
	build(1,1,n);
	while(m--){
		int back,op,pos;
		cin >> back>>op>>pos;
		int nowroot=root[back];
		if(op==1){
			int val;
			cin >> val;
			//在back的基础上，将pos改为val，并且成为最新版本？
			root.push_back(change(nowroot,pos,val) );
		}
		else{
			cout<<query(nowroot,pos)<<endl;
			root.push_back(nowroot);
		
		}
	}
} 

静态区间第k大

https://www.luogu.com.cn/problem/P3834
首先我们可以知道，全局第k大，直接维护一个值域线段树即可。
那么不是全局第k大，我们维护前缀值域线段树，很显然是可以通过和差关系表示任意一段的值域线段树。
做法其实就相当于每一次在叶子节点增加一个有该点权值的值，然后可持久化维护。
离散化是必要的
注意添加的时候按原数组从左到右添加，因为这样每个历史版本都代表着一个前缀的某个区间内的个数。
代码：（重点在get函数，要传两个根节点进去，才能让sum值正确得出）

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
vector<int>root;
struct node{
	int le,ri,ls,rs,val;
}tree[25000006];
int num[1000006];
int lsh[1000006]; 
int buc[1000006];
void pushup(int rt){
	tree[rt].val=tree[tree[rt].ls].val+tree[tree[rt].rs].val;
}
int adddot(int x){//新加入一个点,这个点是原来x的点的变形，返回这个点的编号 
	cnt++;
	tree[cnt]=tree[x];
	return cnt;
}
void build(int rt,int l,int r){//建立空的权值线段树 
	tree[rt].le=l;
	tree[rt].ri=r;
	tree[rt].val=0;
	if(l==r){
		return;
	}
	tree[rt].ls=++cnt;
	tree[rt].rs=++cnt;
	int mid=(l+r)>>1;
	build(tree[rt].ls,l,mid);
	build(tree[rt].rs,mid+1,r);
}
int change(int rt,int x,int val){
	int now=adddot(rt);
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(le==ri){
		tree[now].val=val;
		return now;
	}
	int mid =(le+ri)>>1;
	if(x<=mid){
		tree[now].ls=change(tree[rt].ls,x,val);
	}
	else{
		tree[now].rs=change(tree[rt].rs,x,val);
	}
	pushup(now);
	return now;
}
int get(int Lrt,int Rrt,int k){
	int Lls=tree[Lrt].ls;
	int Lrs=tree[Lrt].rs;
	int Rls=tree[Rrt].ls;
	int Rrs=tree[Rrt].rs;
	int lsum=tree[Rls].val-tree[Lls].val;
	if(tree[Rrt].le==tree[Rrt].ri){
		return tree[Rrt].le;
	}
	if(lsum<k){
		return get(Lrs,Rrs,k-lsum);
	}
	else{
		return get(Lls,Rls,k);
	}
}
int main(){
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> num[i];
		lsh[i]=num[i];
	}
	sort(lsh+1,lsh+1+n);
	int cntt=unique(lsh+1,lsh+1+n)-lsh-1;
	root.push_back(0);
	build(0,1,cntt);//建立一个全部为0的树 
	for(int i=1;i<=n;i++){
		num[i]=lower_bound(lsh+1,lsh+1+cntt,num[i])-lsh;
		buc[num[i]]++;
		int nowroot=root[i-1];
		root.push_back(change(nowroot,num[i],buc[num[i]]));
	}
	while(m--){
		int l,r,k;
		cin >> l >> r >> k;
		cout<<lsh[get(root[l-1],root[r],k)]<<endl;
	}

	
} 

更多应用：（其实就是加了一点其他模板）

和树dfs一起出：

https://www.luogu.com.cn/problem/P2633
可以发现这道题是在树上搞的，因此这个大的区间好像是一段一段的。显然用前缀和已经不够了！
但是这个竟然是树上路径的话，就总会想到一些公式......
特别是dis_L+dis_R-2*dis_lca这个公式。
这个东西，发现是可以搬到这一道题的。
就是想要你求一个点到根节点上所有点的值域线段树然后和差做,相比于上一道题而言，就是get函数里面好像还要多一个root。
实现的话，要稍微想一想。（可以在这里停下来想一下哈）

首先为了不多不少得到树的一点到根上的所有信息，我肯定优先选择dfs噻。
但是dfs存在往回走的情况，这种回退其实可以发现就很像回归某个历史版本的操作。
那我们如何知道以哪一个点结尾时创造出的新的树的树根在原数组（存树根的地方）的具体位置呢？
发现和dfn有较大关系
想到这里应该就好实现啦！
就是要注意，lca那个点，需要额外添加一下。不然就是要点权转边权这么做，不然就是再改一下柿子维护四个根。
我最开始用的第一种，然后痛苦wa掉了。
于是我现在用的第三种。
调了半天才发现有个falcals打成了falcars

#include<bits/stdc++.h>

using namespace std;
int cnt=0;
vector<int>root;
struct node{
	int le,ri,ls,rs,val;
}tree[45000000];//17*100000+100000=1800000
int num[100006];
int lsh[100006]; 
int buc[100006];
int dotval[100005];
void pushup(int rt){
	tree[rt].val=tree[tree[rt].ls].val+tree[tree[rt].rs].val;
}
int adddot(int x){//新加入一个点,这个点是原来x的点的变形，返回这个点的编号 
	cnt++;
	tree[cnt]=tree[x];
	return cnt;
}
void build(int rt,int l,int r){//建立空的权值线段树 
	tree[rt].le=l;
	tree[rt].ri=r;
	tree[rt].val=0;
	if(l==r){
		return;
	}
	tree[rt].ls=++cnt;
	tree[rt].rs=++cnt;
	int mid=(l+r)>>1;
	build(tree[rt].ls,l,mid);
	build(tree[rt].rs,mid+1,r);
}
int change(int rt,int x,int val){
	int now=adddot(rt);
	int le=tree[rt].le;
	int ri=tree[rt].ri;
	if(le==ri){
		tree[now].val=val;
		return now;
	}
	int mid =(le+ri)>>1;
	if(x<=mid){
		tree[now].ls=change(tree[rt].ls,x,val);
	}
	else{
		tree[now].rs=change(tree[rt].rs,x,val);
	}
	pushup(now);
	return now;
}
int get(int Lrt,int Rrt,int lcart,int falca,int k){
	int le=tree[Lrt].le;
	int ri=tree[Lrt].ri;
	if(le==ri){
		return le;
	}
	int Lls=tree[Lrt].ls;
	int Lrs=tree[Lrt].rs;
	int Rls=tree[Rrt].ls;
	int Rrs=tree[Rrt].rs;
	int lcals=tree[lcart].ls;
	int lcars=tree[lcart].rs;
	int falcals=tree[falca].ls;
	int falcars=tree[falca].rs;
	int lsum=tree[Lls].val+tree[Rls].val-tree[lcals].val-tree[falcals].val;
	if(lsum<k){
		return get(Lrs,Rrs,lcars,falcars,k-lsum);
	}
	else{
		return get(Lls,Rls,lcals,falcals,k);
	}
}
//----------------------------------------------------主席树部分

vector<int>mp[100005]; 
int tt=0;
int dfn[100005];
int fat[100005][18];
int dep[100005];
void dfs(int x,int fa){
	//这里是在为lca进行准备 
	dep[x]=dep[fa]+1;
	fat[x][0]=fa;
	for(int i=1;i<=17;i++){
		fat[x][i]=fat[fat[x][i-1]][i-1];
	}
	//接下来实在为主席树做准备 
	tt++;
	dfn[x]=tt;
	root.push_back(change(root[dfn[fa]],dotval[x],++buc[dotval[x]]));
	
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i];
		if(to==fa){
			continue;
		}
		dfs(to,x);
		
	}
	--buc[dotval[x]];//回去时，要消除历史记录。 
}
int getlca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}//让x在上方 
	for(int i=17;i>=0;i--){

		if((dep[y]-(1<<i))>=dep[x]){
			y=fat[y][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=17;i>=0;i--){
        if(fat[x][i]==fat[y][i])//因为可能都跳过了 
            continue;
        else{
        	x=fat[x][i];
			y=fat[y][i];
		}
            
    }
    return fat[x][0];
	
}
int main(){
//	freopen("P2633_1.in","r",stdin);
//	freopen("源程序输出.out","w",stdout);
	int last=0;
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	root.push_back(0);
	for(int i=1;i<=n;i++){
		cin >> dotval[i]; 
		lsh[i]=dotval[i];
	}
	sort(lsh+1,lsh+1+n);
	int cntt=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++){
		dotval[i]=lower_bound(lsh+1,lsh+1+cntt,dotval[i])-lsh;
	}
	build(0,1,cntt);
	for(int i=1;i<=n-1;i++){
		int a,b;
		cin >> a >> b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	dfs(1,0);
	while(m--){
		int u,v,k;
		cin >> u >> v >> k;
		u=(u^last);
		int lcart=getlca(u,v);
		last=lsh[get(root[dfn[u]],root[dfn[v]],root[dfn[lcart]],root[dfn[fat[lcart][0]]],k)];
		cout<<last<<endl;
	}
	
} 

一些总结：

主席树主要用于求解一段区间内第k大的问题。
常常这一段区间需要和差关系来搞，就如2/3两题的和差关系。
还有你会发现，我三个代码的主席树部分基本没怎么变，是个完全可以死记硬背的算法！