众所周知,线段树最重要的操作之一便是标记下传。
但在一些情况下,我们不能进行标记的下传(可能是正确性的问题、或者是复杂度的问题)
正确性问题:比如带修的可持久化线段树中,如果标记下传,会影响之前的版本。
复杂度问题:比如树套树中,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