学步园

http://poj.org/problem?id=3468

#include<stdio.h>
#include<string.h>
#define maxn 100005
#define lc 2*o,l,m
#define rc 2*o+1,m+1,r
long long  data[maxn];
long long  sum[maxn*4];
long long  lazy[maxn*4];
void pushup(int o){
	sum[o]=sum[2*o]+sum[2*o+1];
}
void pushdown(int o,int m){
	if(lazy[o]){
		lazy[2*o+1]+=lazy[o];
		lazy[2*o]+=lazy[o];
		sum[2*o]+=(m-m/2)*lazy[o];
		sum[2*o+1]+=(m/2)*lazy[o];
		lazy[o]=0;
	}
}
void  build(int o,int l,int r){
	lazy[o]=0;
	if(l==r){
		scanf("%lld",&sum[o]);
		return ;
	}
	int m=(l+r)/2;
    build(2*o,l,m);
	build(2*o+1,m+1,r);
	pushup(o);
}
long long query(int L,int R,int o,int l,int r){
	if(L<=l&&R>=r){
		return sum[o];
	}
	//pushdown(o,r-l+1);
    int m=(l+r)/2;
	long long ans=0;
	if(L<=m) ans+=query(L,R,lc);
	if(R>m)   ans+=query(L,R,rc);
	return ans;
}
void update(int L,int R,int c,int o,int l,int r){
	if(L<=l&&r<=R){
		lazy[o]+=c;
		sum[o]+=(long long)c*(r-l+1);
		return ;
	}
	pushdown(o,r-l+1);
	int m=(l+r)/2;
	if(L<=m) update(L,R,c,lc);
	if(R>m) update(L,R,c,rc);
	pushup(o);
}
int main(){
	int n,m;
	int i;
	scanf("%d%d",&n,&m);
	{
		build(1,1,n);
		while(m--)
		{
			getchar();
			char ch;
			scanf("%c",&ch);
			if(ch=='Q')
			{
				int L,R;
				scanf("%d%d",&L,&R);
				printf("%lld\n",query(L,R,1,1,n));
			}
			else
			{
				int L,R,c;
				scanf("%d%d%d",&L,&R,&c);
				update(L,R,c,1,1,n);
			}
		}
	}
	return 0;

}