為了那不可知的詢問永遠(yuǎn)堅(jiān)守于此

解析

眾所周知線段樹的區(qū)間修改是需要打懶標(biāo)記的
多數(shù)時(shí)候，這個(gè)標(biāo)記在詢問子區(qū)間時(shí)需要下傳

而標(biāo)記永久化，就是指不下傳懶標(biāo)記的一種操作
在某些時(shí)候標(biāo)記不便下傳時(shí)有所應(yīng)用
比如zkw線段樹和二維線段樹等
然而zkw線段樹我并不會(huì)
還能起到一定的常數(shù)優(yōu)化作用 （這是真的卡常卡瘋了）

這個(gè)操作是有局限性的
那就是：不可逆性
比如說
標(biāo)記永久化可以維護(hù)區(qū)間賦值和維護(hù)最大值
但前提是區(qū)間賦值必須不小于區(qū)間內(nèi)原來的值
否則就無法操作

細(xì)節(jié)： pushup的時(shí)候一定要把自己身上的懶標(biāo)記考慮在內(nèi)！！

代碼

（線段樹1）

//#include<bits/stdc++.h> #include<cstdio> #include<cctype> #include<algorithm>const int N=5e5+100; const int mod=1e9+7; #define ll long long using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k;#define mid ((l+r)>>1) #define ls (k<<1) #define rs (k<<1|1) ll tr[N<<2],laz[N<<2],a[N]; inline void add(int k,int l,int r,ll v){laz[k]+=v;tr[k]+=(r-l+1)*v;return; } inline void pushup(int k,int l,int r){tr[k]=tr[ls]+tr[rs]+(r-l+1)*laz[k]; } void build(int k,int l,int r){if(l==r){tr[k]=a[l];return;}build(ls,l,mid);build(rs,mid+1,r);pushup(k,l,r);return; } void change(int k,int l,int r,int x,int y,ll v){if(x<=l&&r<=y){//printf("add:(%d %d)\n",l,r);add(k,l,r,v);return;}if(x<=mid) change(ls,l,mid,x,y,v);if(y>mid) change(rs,mid+1,r,x,y,v);pushup(k,l,r);return; } ll ask(int k,int l,int r,int x,int y){if(x<=l&&r<=y) return tr[k];ll res=(min(y,r)-max(x,l)+1)*laz[k];if(x<=mid) res+=ask(ls,l,mid,x,y);if(y>mid) res+=ask(rs,mid+1,r,x,y);//printf("(%d %d) res=%lld\n",l,r,res);return res; } int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);for(int i=1;i<=m;i++){char c;int x,y,z;scanf(" %c%d%d",&c,&x,&y);if(c=='Q') printf("%lld\n",ask(1,1,n,x,y));else{z=read();change(1,1,n,x,y,z);}}return 0; } /* 5 3 7 1 4 1 9 1 3 5 3 1 1 4 2 2 3 5 */

總結(jié)

以上是生活随笔為你收集整理的模板：线段树标记永久化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。