POJ 3468 A Simple Problem with Integers(线段树区间更新)

#include <iostream>
#include <cstdio>
#include <cstring>
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
#define maxn 100005
#define ll long long
using namespace std;
int n,m;
ll pre[maxn << 2],add[maxn << 2];
string str;

void Pushup(ll o){
  pre[o] = pre[o << 1] + pre[o << 1 | 1];
}

void Pushdown(ll o,ll ans){
  if(add[o]){
    add[o << 1] += add[o];         // 注意是+=
    add[o << 1 | 1] += add[o];
    pre[o << 1] += add[o] * (ans - (ans >> 1));
    pre[o << 1 | 1] += add[o] * (ans >> 1);
    add[o] = 0;
  }
}

void Build(ll l,ll r,ll o){
  add[o] = 0;
  if(l == r){
    scanf("%lld",&pre[o]);
    return ;
  }
  ll mid = (l + r) >> 1;
  Build(lson);
  Build(rson);
  Pushup(o);
}

void Update(ll L,ll R,ll ans,ll l,ll r,ll o){
  if(L <= l && r <= R){
    pre[o] += ans * (r - l + 1);
    add[o] += ans;
    return ;
  }
  Pushdown(o, r - l + 1);
  ll mid = (l + r) >> 1;
  if(L <= mid)Update(L,R,ans,lson);
  if(R > mid)Update(L,R,ans,rson);
  Pushup(o);
}

ll Query(ll L,ll R,ll l,ll r,ll o){
  if(L <= l && r <= R){
    return pre[o];
  }
  ll mid = (l + r) >> 1;
  Pushdown(o,r - l + 1);
  ll ans = 0;
  if(L <= mid) ans += Query(L,R,lson);
  if(R > mid) ans += Query(L,R,rson);
  return ans;
}

int main()
{
  scanf("%d%d",&n,&m);
  Build(1,n,1);
  while(m--){
    cin>>str;
    if(str == "Q"){
      ll a,b;
      scanf("%lld%lld",&a,&b);
      printf("%lld\n",Query(a,b,1,n,1));
    }
    else{
      ll a,b,c;
      scanf("%lld%lld%lld",&a,&b,&c);
      Update(a,b,c,1,n,1);
    }
  }
  return 0;
}