线段树标记永久化-白红宇的个人博客

线段树标记永久化

发布日期：2021-09-25 23:58:09 浏览次数：2 分类：技术文章

本文共 1568 字，大约阅读时间需要 5 分钟。

永久化标记就是不需要下传lazy标记，修改的时候一路更改要改的点，询问的时候累加标记即可。

这里以区间赋值为例，注意modify的时候不需要pushup。

#pragma GCC optimize(2)#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;struct Node{ int l,r; LL sum,lazy;}tr[N<<2];void pushup(int u){ tr[u].sum=tr[L].sum+tr[R].sum;}void build(int u,int l,int r){ tr[u]={ l,r,0}; if(l==r) { int x; scanf("%d",&x); tr[u]={ l,r,x,0}; return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u);}void modify(int u,int l,int r,LL c){ tr[u].sum+=(r-l+1)*c; if(tr[u].l==l&&tr[u].r==r) { tr[u].lazy+=c; return; } int mid=l+r>>1; if(r<=Mid) modify(L,l,r,c); else if(l>Mid) modify(R,l,r,c); else modify(L,l,Mid,c),modify(R,Mid+1,r,c);}LL query(int u,int l,int r,LL add){ if(tr[u].l==l&&tr[u].r==r) return tr[u].sum+(r-l+1)*add; if(r<=Mid) return query(L,l,r,add+tr[u].lazy); else if(l>Mid) return query(R,l,r,add+tr[u].lazy); else return query(L,l,Mid,add+tr[u].lazy)+query(R,Mid+1,r,add+tr[u].lazy);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); build(1,1,n); while(m--) { int op,x,y; LL k; scanf("%d%d%d",&op,&x,&y); if(op==1) { scanf("%lld",&k); modify(1,x,y,k); } else printf("%lld\n",query(1,x,y,0)); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108419651 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：李超线段树

下一篇：P4396 [AHOI2013]作业莫队 + 树状数组

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章