线段树出了名的操作是lazy标记。

普通lazy标记涉及到pushup和pushdown

这个pushup只涉及两个儿子合并，并且两个儿子是两个点。

但是有的时候，两个儿子是两个树，pushup复杂度就爆炸了。

给你一个线段树的树套树，外层的线段树pushup一下，就对应里面每个节点对应pushup。O(n^2log^2n)优秀数据结构诞生辣

 

还有的时候，主席树要区间修改。

每次修改操作我们在之前基础上建一棵新树，问题是，儿子是共用的，pushdown一下，之前的版本也会受到影响。凉凉。

 

所以要标记永久化。

 

标记永久化，就是标记不用pushdown，自然也不用pushup（开始建树的时候，可能要pushup）

 

以一维线段树区间加，区间求和为例。

add懒标记，sum是和。

upda时候，路上的sum都加上c*len；如果到了该返回的完全包含节点时候，再把add加上c。

query的时候，把路上的add都做和，到了该返回的节点的时候，返回sum[x]+addsum*len（注意这一层的add别加了就）

可以发现，一路统计，一路标记下来，add，sum有机配合，就可以算出了。

可以理解为，query的时候，在x节点的父亲做过的赋值用add求了出来，x子孙做过的赋值sum已经处理完毕。所以没有问题。

 

真正的例子：

[POI2006]TET-Tetris 3D

二维线段树，矩形求max，矩形取max

（ps：这个题不是矩形取max的话，如果是矩形赋值，标记永久化还真做不了。。）

外层行，内层列。

对于外层的线段树，这个是不能懒标记的。

类比上面开两个变量，这里我们开两个树。

一个mx树，节点上的内层线段树记录这若干行压缩起来的最大值

一个tag树，节点上。。。。。。。。。。。。所打标记的最大值

然后update，query类比即可 。

 

内层线段树由于儿子就是两个点，所以随意了。

 

代码：（空间玄学，反正卡着边界能过）

#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') #define mid ((l+r)>>1) using namespace std; typedef long long ll; il void rd(int &x){char ch;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } namespace Miracle{ const int N=1050; int n,m,k; struct node{int ans[2*N],laz[2*N];void upda(int x,int l,int r,int L,int R,int c){ans[x]=max(ans[x],c);if(L<=l&&r<=R) {laz[x]=max(laz[x],c);return;}if(L<=mid) upda(x<<1,l,mid,L,R,c);if(mid<R) upda(x<<1|1,mid+1,r,L,R,c);}int query(int x,int l,int r,int L,int R){if(L<=l&&r<=R){return ans[x];}int ret=laz[x];if(L<=mid) ret=max(ret,query(x<<1,l,mid,L,R));if(mid<R) ret=max(ret,query(x<<1|1,mid+1,r,L,R));return ret;} }mx[2*N],tag[2*N]; void upda(int x,int l,int r,int l1,int r1,int l2,int r2,int c){mx[x].upda(1,1,m,l2,r2,c);if(l1<=l&&r<=r1){tag[x].upda(1,1,m,l2,r2,c);return;}if(l1<=mid) upda(x<<1,l,mid,l1,r1,l2,r2,c);if(mid<r1) upda(x<<1|1,mid+1,r,l1,r1,l2,r2,c); } int query(int x,int l,int r,int l1,int r1,int l2,int r2){if(l1<=l&&r<=r1) return mx[x].query(1,1,m,l2,r2);int ret=tag[x].query(1,1,m,l2,r2);if(l1<=mid) ret=max(ret,query(x<<1,l,mid,l1,r1,l2,r2));if(mid<r1) ret=max(ret,query(x<<1|1,mid+1,r,l1,r1,l2,r2));return ret; } int main(){rd(n);rd(m);rd(k);int x,y,s,d,h;while(k--){rd(d);rd(s);rd(h);rd(x);rd(y);++x,++y;int ch=query(1,1,n,x,x+d-1,y,y+s-1)+h;upda(1,1,n,x,x+d-1,y,y+s-1,ch);}printf("%d",query(1,1,n,1,n,1,m));return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2018/12/9 18:33:23 */

 ps：感觉如果值不具有覆盖性（取max）或者等价撤销性（加减），就不能标记永久化了（赋值）

转载于:https://www.cnblogs.com/Miracevin/p/10092806.html

总结

以上是生活随笔为你收集整理的[学习笔记]标记永久化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。