洛谷3372线段树模板题对区间+k或者查询区间和

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef unsigned int ui;
  4 typedef long long ll;
  5 typedef unsigned long long ull;
  6 #define pf printf
  7 #define mem(a,b) memset(a,b,sizeof(a))
  8 #define prime1 1e9+7
  9 #define prime2 1e9+9
 10 #define pi 3.14159265
 11 #define lson l,mid,rt<<1
 12 #define rson mid+1,r,rt<<1|1
 13 #define scand(x) scanf("%llf",&x) 
 14 #define f(i,a,b) for(int i=a;i<=b;i++)
 15 #define scan(a) scanf("%d",&a)
 16 #define dbg(args) cout<<#args<<":"<<args<<endl;
 17 #define pb(i) push_back(i)
 18 #define ppb(x) pop_back(x)
 19 #define inf 0x3f3f3f3f
 20 #define maxn 100005
 21 int n,m,t;
 22 ll sum[maxn<<2],add[maxn<<2];
 23 void pushup(int rt)//上拉 
 24 {
 25     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 26  } 
 27 void build(int l,int r,int rt)
 28 {
 29     if(l==r)
 30     {
 31         scanf("%lld",&sum[rt]); 
 32         return ;
 33     }
 34     int mid=l+r>>1;
 35     build(lson);
 36     build(rson);
 37     pushup(rt);//上拉，维护区间和 
 38 }
 39 void pushdown(int rt,int ln,int rn)//lazy tag下推 
 40 {
 41     if(add[rt])
 42     {
 43         add[rt<<1]+=add[rt];//+=表示该段原先可能就有没有下推的lazy tag 
 44         add[rt<<1|1]+=add[rt];
 45         
 46         sum[rt<<1]+=add[rt]*ln;//一旦lazy tag加到这段区间上就代表区间的sum是准确更新过的 
 47         sum[rt<<1|1]+=add[rt]*rn; 
 48         add[rt]=0;//lazytag完成转移 
 49     }
 50 }
 51 void update(int l,int r,int rt,int L,int R,ll C)
 52 {
 53     if(L<=l&&r<=R)
 54     {
 55         add[rt]+=C;//tag到达之处维护的值也相对应的更新 
 56         sum[rt]+=C*(r-l+1);
 57         return;
 58     }
 59     int mid=l+r>>1;
 60     //在更新子结点之前下推标记，保证更新直到最终结点之前的结点lazytag全部下推 
 61     pushdown(rt,mid-l+1,r-mid);
 62     if(L<=mid) update(lson,L,R,C);
 63     if(R>mid) update(rson,L,R,C);
 64     pushup(rt);//更新完子节点之后在更新父节点整个update才结束 
 65 }
 66 ll query(int l,int r,int rt,int L,int R)
 67 {
 68     if(L<=l&&r<=R)
 69     {
 70         return sum[rt];
 71     }
 72     int mid=l+r>>1;
 73     pushdown(rt,mid-l+1,r-mid);
 74     ll ans=0;
 75     if(L<=mid) ans+=query(lson,L,R);
 76     if(R>mid) ans+=query(rson,L,R);
 77     return ans;    
 78  } 
 79 int main()
 80 {
 81     //freopen("P3372_2.txt","r",stdin);
 82     //freopen("output.txt","w",stdout);
 83     std::ios::sync_with_stdio(false);
 84     scan(n);scan(m);
 85     build(1,n,1);
 86     int flag,l,r;
 87     ll k;
 88     while(m--)
 89     {
 90         scan(flag);
 91         if(flag==1)
 92         {
 93             scanf("%d%d%lld",&l,&r,&k);
 94             update(1,n,1,l,r,k);
 95         }
 96         else if(flag==2)
 97         {
 98             scan(l);scan(r);
 99             pf("%lld
",query(1,n,1,l,r));
100         }
101      } 
102  }
洛谷3372线段树模板题 对区间+k或者查询区间和

洛谷3372线段树模板题对区间+k或者查询区间和
