首页 > 其他分享 >标记永久化【学习笔记】

标记永久化【学习笔记】

时间:2024-02-26 17:11:07浏览次数:29  
标签:rt qr 标记 int ll tr 笔记 永久化 ql

众所周知,线段树最重要的操作之一便是标记下传。
但在一些情况下,我们不能进行标记的下传(可能是正确性的问题、或者是复杂度的问题)
正确性问题:比如带修的可持久化线段树中,如果标记下传,会影响之前的版本。
复杂度问题:比如树套树中,push_up操作的复杂度会直接炸掉。
因此,就产生了标记永久化这一方法。
顾名思义,标记永久化就是免去了上传或下传操作。
以区间加、区间和为例子
在update中:每次遍历到的节点都直接更新权值,在最后完全包含的节点更新懒标记。
在query中:每次在完全包含的节点上,都返回这个节点的权值+其所有祖先节点的懒标和*区间长度
给出一份参考代码

#include<bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define ll long long
int n,m,a[100005];
struct tree{
	ll v,lz;
}tr[400005];
void push_up(int rt){
	tr[rt].v=tr[ls].v+tr[rs].v;
}
void build(int rt,int l,int r){
	if(l==r){
		tr[rt].v=a[l];
		return ;
	}
	tr[rt].lz=0;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(rt);
}
void update(int rt,int l,int r,int ql,int qr,ll k){
	tr[rt].v+=k*(min(r,qr)-max(l,ql)+1);
	if(ql<=l && qr>=r){
		tr[rt].lz+=k;
		return ;
	}
	if(ql<=mid)update(ls,l,mid,ql,qr,k);
	if(qr>mid)update(rs,mid+1,r,ql,qr,k);
}
ll query(int rt,int l,int r,int ql,int qr,ll lzs){
	if(ql<=l && qr>=r)return tr[rt].v+(r-l+1)*lzs;
	ll res=0;
	if(ql<=mid)res+=query(ls,l,mid,ql,qr,lzs+tr[rt].lz);
	if(qr>mid)res+=query(rs,mid+1,r,ql,qr,lzs+tr[rt].lz);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r;scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			ll k;scanf("%lld",&k);
			update(1,1,n,l,r,k);
		}else printf("%lld\n",query(1,1,n,l,r,0));
	}
	return 0;
} 

example

1.SP11470 TTM - To the moon
传送门(spoj)
传送门(luogu)

其实就是个带修的可持久化线段树
为了防止影响以前的版本,需要加一个标记永久化

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (l+r>>1)
#define lson tr[rt].ls
#define rson tr[rt].rs
#define ls1 tr[rt1].ls
#define ls2 tr[rt2].ls
#define rs1 tr[rt1].rs
#define rs2 tr[rt2].rs
int n,m,a[100005];
struct node{
	int ls,rs,lz;
	ll v;
}tr[8000005];
int tot,ut,rot[100005];
void push_up(int rt){
	tr[rt].v=tr[lson].v+tr[rson].v;
}
void build(int rt,int l,int r){
	if(l==r){
		tr[rt].v=a[l];
		return ;
	}
	lson=++tot;build(lson,l,mid);
	rson=++tot;build(rson,mid+1,r);
	push_up(rt);
}
void update(int rt1,int rt2,int l,int r,int ql,int qr,int k){
	tr[rt1]=tr[rt2];
	tr[rt1].v+=1LL*k*(min(r,qr)-max(l,ql)+1);
	if(ql<=l && qr>=r){
		tr[rt1].lz+=k;
		return ;
	}
	if(ql<=mid){
		ls1=++tot;
		update(ls1,ls2,l,mid,ql,qr,k);
	}else ls1=ls2;
	if(qr>mid){
		rs1=++tot;
		update(rs1,rs2,mid+1,r,ql,qr,k);
	}else rs1=rs2;
}
ll query(int rt,int l,int r,int ql,int qr,ll lzs){
	if(ql<=l && qr>=r)return tr[rt].v+lzs*(r-l+1);
	ll res=0;
	if(ql<=mid && lson)res+=query(lson,l,mid,ql,qr,lzs+tr[rt].lz);
	if(qr>mid && rson)res+=query(rson,mid+1,r,ql,qr,lzs+tr[rt].lz);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	rot[0]=++tot;build(1,1,n);
	for(int i=1;i<=m;i++){
		char op[5];scanf("%s",op+1);
		if(op[1]=='C'){
			int l,r,d;scanf("%d%d%d",&l,&r,&d);
			ut++;rot[ut]=++tot;
			update(rot[ut],rot[ut-1],1,n,l,r,d);
		}else if(op[1]=='Q'){
			int l,r;scanf("%d%d",&l,&r);
			printf("%lld\n",query(rot[ut],1,n,l,r,0));
		}else if(op[1]=='H'){
			int l,r,t;scanf("%d%d%d",&l,&r,&t);
			printf("%lld\n",query(rot[t],1,n,l,r,0));
		}else if(op[1]=='B'){
			int t;scanf("%d",&t);
			ut=t;
		}
	}
	return 0;
} 

后面树套树中的标记永久化,由于我不会树套树,所以不写了(待会学一下splay、treap,就去学树套树)

标签:rt,qr,标记,int,ll,tr,笔记,永久化,ql
From: https://www.cnblogs.com/kentsbk/p/18034747

相关文章

  • 古人云:时间线段树 爽!时间线段树学习笔记。
    嘛,这个东西虽然叫时间线段树,但是和线段树好像关系并不大,只是借用了一下线段树的结构。算法介绍这个算法是用来解决这类问题的:每个操作只在一段时间内生效,然后询问某个时间点所有操作的贡献。于是我们考虑离线,对整个时间序列建一个线段树,每次操作相当于是在这个线段树上进行了区......
  • 容斥原理学习笔记
    前言可能需要一点二项式定理和二项式反演的相关知识。有许多不足还请指出。公式经典容斥\(A_1,A_2,\cdots,A_n\)均为有限集,\(A_i\subseteqS\),则\[\left\vert\bigcup\limits_{i=1}^nA_i\right\vert=\sum\limits_{k=1}^n(-1)^{k-1}\sum\limits_{1\lei_1<i_2<\cdots<i_k\le......
  • MAUI Blazor+MASA开发安卓应用学习笔记 - 设置图标和初始屏幕
    上一期已经成功生成了APK能成功安装到手机上了,图标和初始屏幕很难看,接下来着手修改图标和初始屏幕一、修改图标打开项目文件.csproj,找到以下代码<!--AppIcon--><MauiIconInclude="Resources\AppIcon\appicon.svg"ForegroundFile="Resources\AppIcon\appiconfg.svg"Colo......
  • Vue 学习笔记15--用户代码片段
    { //Placeyour全局snippetshere.Eachsnippetisdefinedunderasnippetnameandhasascope,prefix,bodyand //description.Addcommaseparatedidsofthelanguageswherethesnippetisapplicableinthescopefield.Ifscope //isleftemptyor......
  • MAUI Blazor+MASA开发安卓应用学习笔记 - 设置APP格式、名称、版本信息
    上一期说到了如何生成APP应用,生成的文件是AAB格式的,这个格式安装不是很方便,如果能生成APK就好了 一、设置APP格式打开项目文件.csproj,在PropertyGroup下添加属性<AndroidPackageFormat>apk</AndroidPackageFormat>二、设置名称和版本信息在项目文件里,可以设置全局的应用......
  • MAUI Blazor+MASA开发安卓应用学习笔记 - 新建项目和发布
    PS:开个新坑,内容都是全新接触的东西,包括MAUI,Blazor,MASA等等。整个项目都边学习边做的,有什么错的地方望大神指教。 学习开发安卓应用,我们的最终目标就是要生成一个APP应用,并能成功的在手机端打开。那么,我们首先要解决的就是怎么生成APP应用。一、创建一个.NETMAUIBlazor应用(注......
  • 万字Java进阶笔记总结
    JavaApi字符串String注意:Java中“==”操作符的作用:基本数据类型:比较的是内容。引用数据类型比较的是对象的内存地址。StringBuffer/StringBuilder由于String是字符串是常量,它们的值在创建之后不能更改。如果我们使用这个String频繁进行操作,会有性能问题,这个时候就需要......
  • 《系统科学方法概论》第五章读书笔记
    首先,组建现代管理系统必须遵循远离平衡态原则。这也就是说,构成管理系统的人员必须具有各不相同的能力和水平,尤其是作为管理系统的第一把手应具备把握全局的能力和权力,而其他成员则不必具备把握全局的能力和权力,或只需具备把握某-方面全局的能力和权力即可。如果-一个管理系统的所......
  • 《系统科学方法概论》第二章读书笔记
    系统工程不是无缘无故地提出的,而是为了解决目前实践或科研中所遇到的问题而搞起来的。所以,在设计或研制一项系统工程前,应先把所遇到的问题搞清楚。问题是什么?就是现实状况和主观需要之间的矛盾。在阐述问题时,要注意三个方面:-是注意问题的过去、现在和将来的发展趋势,也就是要考......
  • 《系统科学方法概论》第三章读书笔记
    信息论最初是作为一种通信理论而被建立起来的,它也主要用于通信领域。但是经过30多年的发展,到了20世纪70年代,信息论已不仅仅是一种通信理论,而是越过了通信领域,广泛渗人其他学科了。例如在物理学研究中,一些科学家就把信息与熵1]联系起来,以说明系统的有序和无序的相互转化。在生物学......