poj 3468-セグメントツリー

#include
#include
#include
#include
#include
#include
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int mx = 1e5+10;
ll num[mx<<2],sum[mx<<2];
char str[10];
void build(int l,int r,int rt){
	if(l==r){
		scanf("%lld",num+rt);
		return ;
	}
	int mid = (l+r)>>1;
	build(lson);
	build(rson);
	num[rt] = num[rt<<1]+num[rt<<1|1];
}
void Split(int rt,int len){
	if(sum[rt]){
		sum[rt<<1]+=sum[rt];
		sum[rt<<1|1]+=sum[rt];
		num[rt<<1]+=sum[rt]*(len-len/2);
		num[rt<<1|1]+=sum[rt]*(len/2);
		sum[rt]=0;
	}
} 
ll query(int L,int R,int l,int r,int rt){
	if(L<=l&&R>=r) return num[rt];
	Split(rt,r-l+1);
	int mid = (l+r)>>1;
	ll ans = 0;
	if(L<=mid) ans+=query(L,R,lson);
	if(R>mid)  ans+=query(L,R,rson);
	return ans;
}
void update(int L,int R,int l,int r,int rt,int v){
	if(L<=l&&R>=r){
		sum[rt]+=v;
		num[rt]+=(r-l+1)*v;
		return ;
	}
	int mid = (l+r)>>1;
	Split(rt,r-l+1);// , ; 
	if(L<=mid) update(L,R,lson,v);
	if(R>mid)  update(L,R,rson,v);
	num[rt] = num[rt<<1]+num[rt<<1|1];
}
int main(){
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		memset(sum,0,sizeof(sum));
		build(1,n,1);
		int x,y;
		while(m--){
			scanf("%s%d%d",str,&x,&y);
			if(str[0]=='Q')  printf("%lld
",query(x,y,1,n,1));
			else{
				int v;
				scanf("%d",&v);
				update(x,y,1,n,1,v);
			}
		}
	} 
	return 0;
}