首页 > 其他分享 >主席树（更新）

主席树（更新）

时间：2023-10-25 17:22:32浏览次数：39  
标签：rt le val int tree 更新 ri 主席

主席树学习

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

目录

背景：

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两题的和差关系。
还有你会发现，我三个代码的主席树部分基本没怎么变，是个完全可以死记硬背的算法！

更新内容(2023/10/25)

区间修改（持久化tag)

这里主要是介绍区间修改的问题。
例题为to the moon 这道题(注意是多组数据哦）
他要求区间修改，还有历史状态。这里要写持久化lz（tag)
什么意思呢？
就是在change 复制了原始时间的所有值后，这个节点本身直接修改，lazy直接修改但是不下放。
然后呢？在查询的时候，不仅要加上这个节点的val,还要加上这个节点lazy提供的信息。具体可看下面的query，它的第三部分就是加的lazy。
然后其他的和单点修改差不多，就是你区间内只要修改了就新建，没动过一点就连原来的。
当然有一个小细节
就是说我新建的节点不能pushup。（我代码中注释的部分）
为什么呢？首先因为你每个节点都是在原来情况下复制的并且已经加上了一部分权值了。
如果pushup的话，就把加了的再加一次，就错了（大概？）。
放代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
总结就是：区间内存在新修改的段落的，就直接新建，否则链接
然后标记永久化就是打在那里不下传，每次走过的时候加权值就好 
*/
int a[100005];
int cnt;
struct node{
	int ls;
	int rs;
	int val;
	int lz;
}tree[3000005];
void pushup(int rt){
	tree[rt].val=tree[tree[rt].ls].val+tree[tree[rt].rs].val;
}
void build(int rt,int L,int R){
	if(L==R){
		tree[rt].val=a[L];
		tree[rt].lz=0;
		return;
	}
	tree[rt].lz=0;
	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);
	pushup(rt);
}
int newnode(int rt){
	cnt++;
	tree[cnt]=tree[rt];
	return cnt;
} 
int change(int prert,int L,int R,int le,int ri,int vl){
	if(le>R||ri<L){
		return prert;
	}
	int now=newnode(prert);
	if(le>=L&&ri<=R){
		tree[now].lz+=vl;
		tree[now].val+=vl*(ri-le+1);
		return now;
	}
	else{
		tree[now].val+=vl*(max(0ll,min(R,ri)-max(L,le)+1));//那一部分要修改
		int mid=(le+ri)>>1;
		tree[now].ls=change(tree[prert].ls,L,R,le,mid,vl);
		tree[now].rs=change(tree[prert].rs,L,R,mid+1,ri,vl);
//		pushup(now);
		return now; 
	}
	
}
int query(int rt,int L,int R,int le,int ri){
	if(le>R||ri<L){
		return 0;
	}
	if(le>=L&&ri<=R){
		return tree[rt].val;
	}
	else{
		int ret=0;
		int mid=(le+ri)>>1;
		ret+=query(tree[rt].ls,L,R,le,mid);
		ret+=query(tree[rt].rs,L,R,mid+1,ri);
		ret+=tree[rt].lz*(max(0ll,min(R,ri)-max(L,le)+1));
		return ret;
	}
}
int tt[100005];
int dt=1;
int now=1;
signed main(){
//	freopen("moon1.in","r",stdin);
//	freopen("ans.out","w",stdout);
	ios::sync_with_stdio(false);
	int n,m;
	while(cin >> n){
		dt=1;
		now=1;
		cin >> m;
		for(int i=1;i<=n;i++){
			cin >> a[i];
		} 
		cnt=1;
		build(1,1,n);
		tt[1]=1;
		while(m--){
			char c;
			cin >> c;
			if(c=='C'){
				int l,r,d;
				cin >> l >> r >> d;
				now++;
				tt[now]=change(tt[now-1],l,r,1,n,d);
			}
			else if(c=='Q'){
				int l,r;
				cin >> l >> r;
				cout<<query(tt[now],l,r,1,n)<<endl;
			}
			else if(c=='H'){
				int l,r,t;
				cin >> l >> r >> t;
				t++;
				cout<<query(tt[t],l,r,1,n)<<endl;
				
			}
			else{
				int t;
				cin >> t;
				t++;
				now=t;
			}
		}	
	} 
	
}

T了一个点加个read就好了。

标签：rt,le,val,int,tree,更新,ri,主席
From： https://www.cnblogs.com/linghusama/p/17697328.html

相关文章

  • RTSP视频流媒体服务器LiteCVR v3.1更新：通道收藏优化
    在安防视频监控行业，监控摄像头也正从"看得见"到"看得清"开始转变，现在的网络智能摄像头，不仅可以拥有高清超高清的监控画质，还能对记录的视频中的人或物体进行识别。近期我们对LiteCVR增加了普通用户的收藏功能，今天来简单介绍一下。在LiteCVRv3.1版本之前，普通用户只能查看分配给自己......
  • RTSP视频监控平台LiteCVR v3.1更新：通道收藏优化
    在安防视频监控行业，监控摄像头也正从"看得见"到"看得清"开始转变，现在的网络智能摄像头，不仅可以拥有高清超高清的监控画质，还能对记录的视频中的人或物体进行识别。近期我们对LiteCVR增加了普通用户的收藏功能，今天来简单介绍一下。在LiteCVRv3.1版本之前，普通用户只能查看分配给......
  • 【AGC】更新应用信息报未知错误解决方法
    ​【问题描述】最近有几个开发者遇到了一个问题，他们在AGC控制台配置好应用信息的图标和截图之后，点击保存按钮会弹出“未知错误，请稍后再试”的异常报错，导致无法正确保存应用配置信息。出错页面如图所示。​​​ 【解决方案】出现“未知错误”的原因有很多，需要根据请求日志具......
  • 【HarmonyOS】元服务卡片展示动态数据，并定点更新卡片数据
    ​ 【关键字】元服务卡片、卡片展示动态数据、更新卡片数据 【写在前面】本篇文章主要介绍开发元服务卡片时，如何实现卡片中动态显示数据功能，并实现定时数据刷新。本篇文章通过实现定时刷新卡片中日期数据为例，讲述展示动态数据与更新数据功能。 【开发步骤】1、在卡片的......
  • 支付宝权限问题大全｜一文搞定，持续更新
    不知道有多少小伙伴还在头疼支付宝权限的问题，这边汇总了下目前对接支付宝可能会出现的权限问题，总有一篇能解决。 前期准备：支付宝赋权要求工欲善其事，必先利其器。这里先介绍下支付宝目前的赋权要求：账号完成对应产品签约——如何签约应用下绑定对应产品——如何查看应......
  • Linux下更新curl版本教程！
    在Linux下更新curl版本，您可以按照以下步骤进行操作：1、检查当前curl版本：首先，您需要确定当前系统中安装的curl版本。打开终端，并执行以下命令：curl--version 该命令将显示当前curl的版本信息。1、确认可用的curl版本：在更新curl之前，您需要确定可用的最新版本。您可以......
  • Win11更新后输入法候选字词不是<>大于/小于号,.逗号/句号
    Win11更新后，会有一些选项恢复为默认，又需要重新设置。一、设置候选字词用大小于号1.在桌面右下角输入法上--右键--按键配置2.将逗号/句号前打勾就可以了二、如果点击按键配置后，没有上图的按键选项。1.点击按键配置后，只显示语言和区域，说明是没有默认的输入法......
  • 安防视频监控平台EasyCVR新版（3.4）平台界面更新2.0
    视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中，将分散的各类视频资源进行统一汇聚、整合、集中管理，在视频监控播放上，TSINGSEE青犀视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放，可同时播放多路视频流，也能支持视频定时轮播。视频监控汇聚平台EasyCVR支持多种播放......
  • 关闭Windows更新
    关闭Windows更新功能的方法有以下几种：1通过设置中的Windows更新选项关闭：打开“设置”应用，选择“更新和安全”，在左侧导航栏中选择“Windows更新”，在“更新设置”下点击“更改活动小时”，将开关从“开”调整为“关”。2通过服务管理关闭Windows更新：按下Win+R组合键，打开运行对话......
  • 主席树初步
    什么是主席树主席树即可持久化线段树这边其实我目前感觉就是支持查询历史版本的线段树原理每当线段树修改时，维护其过去的版本，将其复制下来（然后就MLE了改进：对集合的每一个版本维护一个单独的根，在修改数据时，只复制树的一部分(复制一张别人的图Orz)建树类似......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99