线段树的一些板子

有2种方式，都是用的lazy标记，但具体用法不同

1）标记永久化

假设现在需要

1.区间加值 2.求区间和 

#include <iostream>
#include <algorithm>
using namespace std ;
 const int N=1e5+2;
 
#define int long long 
 
 int sum[N<<2],lazy[N<<2],n,a[N];
 int X,Y,_sum;
 
 void q(int o,int l,int r){
     if(X<=l&&Y>=r){
         _sum+=sum[o]+lazy[o]*(r-l+1); return;
     }
     _sum+=(min(Y,r)-max(l,X)+1)*lazy[o];
     int md=(l+r)/2; 
     if(X<=md) q(o*2,l,md);
     if(Y>md) q(o*2+1,md+1,r);
 }
 void add(int o,int l,int r,int z){
     if(X<=l&&Y>=r){
         lazy[o]+=z;  return;
     }
     sum[o]+=(min(Y,r)-max(l,X)+1)*z;
     int md=(l+r)/2;
     if(X<=md) add(o*2,l,md,z);
    if(Y>md) add(o*2+1,md+1,r,z);
 }
 void build(int o,int l,int r){
     lazy[o]=0;
     if(l==r){
         sum[o]=a[l];  return;
     }
     int md=(l+r)/2;
     build(o*2,l,md); build(o*2+1,md+1,r);
     sum[o]=sum[o*2]+sum[o*2+1];
 }
 signed main(){
 //    freopen("in","r",stdin);
     int i,T,op,z;
     cin>>n>>T;
     for(i=1;i<=n;i++) cin>>a[i];
     build(1,1,n);
     
     while(T--){
         cin>>op>>X>>Y;
           if(op==1){
               cin>>z; add(1,1,n,z);
           }
           else{
               _sum=0;
               q(1,1,n); 
               cout<<_sum<<endl;
           }
     }
 }
 
 

2)标记下传

#define k1 k<<1
#define k2 k<<1|1
#define int long long 
 
 int sum[N<<2],lazy[N<<2],n,a[N];
 
 void help(int k,int l,int r,int v){
     lazy[k]+=v,sum[k]+=(r-l+1)*v;
 }
 void pushd(int k,int l,int r){
     int md=(l+r)/2; 
     if(!lazy[k]) return;
     
     help(k1,l,md,lazy[k]),help(k2,md+1,r,lazy[k]); 
     lazy[k]=0;
 }
 int qry(int k,int l,int r,int x,int y){
     int t=0;
     if(x<=l&&y>=r)
         return sum[k];
     
     int md=(l+r)/2; 
     pushd(k,l,r);
     if(x<=md) t+=qry(k1,l,md,x,y);
     if(y>md) t+=qry(k2,md+1,r,x,y);
     return t;
 }
 void add(int k,int l,int r,int x,int y,int z){
     if(x<=l&&y>=r) return help(k,l,r,z);
     
     int md=(l+r)/2;
     pushd(k,l,r);
     if(x<=md) add(k1,l,md,x,y,z);
    if(y>md) add(k2,md+1,r,x,y,z);
    
     sum[k]=sum[k1]+sum[k2];
 }
 void build(int k,int l,int r){
     if(l==r){
         sum[k]=a[l]; return;
     }
     int md=(l+r)/2;
     build(k1,l,md),build(k2,md+1,r);
     sum[k]=sum[k1]+sum[k2];
 }