#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=(1<<18)-1;
ll data[N],datb[N];

void add(int a,int b,int x,int k,int l,int r){
  if(a<=l&&r<=b) data[k]+=x;
  else if(l<b&&a<r){
     datb[k]+=(min(b,r)-max(a,l))*x;
     add(a,b,x,k*2+1,l,(l+r)/2);
     add(a,b,x,k*2+2,(l+r)/2,r);
  }
}

ll sum(int a,int b,int k,int l,int r){
    if(b<=l||r<=a) return 0;
    else if(a<=l&&r<=b){
        return data[k]*(r-l)+datb[k];
    }
    else{
        ll res=data[k]*(min(b,r)-max(a,l));
        res+=sum(a,b,k*2+1,l,(l+r)/2);
        res+=sum(a,b,k*2+2,(l+r)/2,r);
        return res;
    }
}

int main(){
     int q,n;
     while(~scanf("%d %d",&n,&q)){
        memset(data,0,sizeof(data));
        memset(datb,0,sizeof(datb));
        for(int i=0;i<n;i++){
            int x;scanf("%d",&x);
            add(i,i+1,x,0,0,n);
        }
        //cout<<sum(3,4,0,0,n)<<endl;
        for(int i=0;i<q;i++){
            //getchar();
            char c[2];scanf("%s",c);
            if(c[0]=='C'){
                int l,r,x;scanf("%d%d%d",&l,&r,&x);
                add(l-1,r,x,0,0,n);
            }
            else {
                int l,r;scanf("%d%d",&l,&r);
                printf("%lld\n",sum(l-1,r,0,0,n));
            }
        }
     }
}

• 树状数组AC (566) 770605294 2017-03-20 23:29:48