poj3468 A Simple Problem with Integers（线段树区间更新）

https://vjudge.net/problem/POJ-3468

线段树区间更新（lazy数组）模板题

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define INF 0x3f3f3f3f

 typedef long long ll;

 using namespace std;

 ll sum[<<], lazy[<<];

 void PushUP(int rt)

 {

     sum[rt] = sum[rt<<]+sum[rt<<|];

 }

 void PushDown(int rt, int m)

 {

     if(lazy[rt]){//若有标记下移

         lazy[rt<<] += lazy[rt];

         lazy[rt<<|] += lazy[rt];

         sum[rt<<] += (m-(m>>))*lazy[rt];

         sum[rt<<|] += (m>>)*lazy[rt];

         lazy[rt] = ;//取消本层标记

     }

 }

 void build(int l, int r, int rt)

 {

     lazy[rt] = ;//一定写在if外初始化

     if(l == r){

         scanf("%lld", &sum[rt]);

         return ;

     }

     int m = (l+r)>>;

     build(lson);

     build(rson);

     PushUP(rt);

 }

 ll Query(int L, int R, int l, int r, int rt)

 {

     if(L<=l&&R>=r){

         return sum[rt];

     }

     PushDown(rt, r-l+);//向下更新

     int m = (l+r)>>;

     ll ans=;

     if(L <= m) ans += Query(L, R, lson);

     if(R > m) ans += Query(L, R, rson);

     return ans;

 }

 void Update(int L, int R, ll add, int l, int r, int rt)

 {

     if(L<=l&&R>=r){

         sum[rt] += (r-l+)*add;

         lazy[rt] += add;

         return ;

     }

     PushDown(rt, r-l+);//向下而更新

     int m=(l+r)>>;

     if(L <= m) Update(L, R, add, lson);

     if(R > m) Update(L, R, add, rson);

     PushUP(rt);

 }

 int main()

 {

     int n, m, a, b;

     ll c;

     char op[];

     scanf("%d%d", &n, &m);

     build(, n, );

     for(int i = ; i < m; i++){

         scanf("%s", &op);

         if(op[] == 'Q'){

             scanf("%d%d", &a, &b);

             printf("%lld\n", Query(a, b, , n, ));

         }

         else{

             scanf("%d%d%lld", &a, &b, &c);

             Update(a, b, c, , n, );

         }

     }

     return ;

 }