526互联

主席树学习

发布时间 2023-09-12 17:49:44作者: 铃狐sama

主席树学习

目录

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

背景：

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那个点，需要额外添加一下。不然就是要点权转边权这么做，不然就是再改一下柿子维护四个根。
我用的前一种，添加一个sp来表示这个点的权值，只要他在当前我找的区间内就会产生贡献，然后分类讨论搞他
稍微注意一下，我的代码这么写的话，要特判1，因为我令1的fa还是1，但是应该是0开始。
（现在正在调试，因为全RE嘤嘤嘤）

一些总结：

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