记录编号	89290	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.257 s
提交时间	2014-03-01 12:47:52	内存使用	1.82 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int SIZEN=100010;
class TARRAY{//改段求段的树状数组
public:
	int n;
	ll s[SIZEN];//维护当前[1,i]被整体加了多少,在其子区间里加的不算,需要调用其后缀和
	ll rs[SIZEN];//维护当前[1,i]的和被整体加了多少,需要调用其前缀和
	void clear(int x){n=x;memset(s,0,sizeof(s));memset(rs,0,sizeof(rs));}
	int lowbit(int x){return x&(-x);}
	void prefchange(int x,ll t){
		if(x<1) return;
		for(int i=x;i>0;i-=lowbit(i)) s[i]+=t;
		for(int i=x;i<=n;i+=lowbit(i)) rs[i]+=x*t;
	}
	ll prefsum(int x){
		if(x<1) return 0;
		ll b=0,c=0;
		for(int i=x;i<=n;i+=lowbit(i)) b+=s[i];
		for(int i=x-1;i>0;i-=lowbit(i)) c+=rs[i];
		return b*x+c;
	}
	void change(int l,int r,ll t){
		prefchange(r,t);
		prefchange(l-1,-t);
	}
	ll segsum(int l,int r){
		return prefsum(r)-prefsum(l-1);
	}
};
TARRAY tree;
int N,M;
ll A[SIZEN]={0};
int main(){
	freopen("shuliec.in","r",stdin);
	freopen("shuliec.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lld",&A[i]);
	tree.clear(N);
	for(int i=1;i<=N;i++) tree.change(i,i,A[i]);
	scanf("%d",&M);
	int l,r;
	ll t;
	while(M--){
		string cmd;
		cin>>cmd;
		if(cmd=="SUM"){
			scanf("%d%d",&l,&r);
			printf("%lld\n",tree.segsum(l,r));
		}
		else if(cmd=="ADD"){
			scanf("%d%d%lld",&l,&r,&t);
			tree.change(l,r,t);
		}
	}
	return 0;
}