记录编号	55757	评测结果	AAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.019 s
提交时间	2013-03-21 20:52:52	内存使用	4.51 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
using namespace std;
class SEGMENT{
public:
	int l,r;
	int lchild,rchild;
	int s;
};
int n;
SEGMENT tree[200001];
int d[100001]={0};//每个点的值
int tot=0;
void build(int root,int left,int right){
	tree[root].l=left,tree[root].r=right;
	if(left<right){//继续往下分
		int mid=(left+right)/2;
		tree[root].lchild=++tot;
		build(tot,left,mid);
		tree[root].rchild=++tot;
		build(tot,mid+1,right);
		tree[root].s=tree[tree[root].lchild].s+tree[tree[root].rchild].s;
	}
	else{
		tree[root].s=d[left];
		tree[root].lchild=tree[root].rchild=-1;
	}
}
void add(int root,int x,int s){//在root里把x这个节点加上s
	if(root==-1||tree[root].l>x||tree[root].r<x) return;//不包含是要闹哪样
	tree[root].s+=s;
	add(tree[root].lchild,x,s);
	add(tree[root].rchild,x,s);
}
int getsum(int root,int x,int y){//在root这个节点里面查找[x,y]的区间和
	if(root==-1||tree[root].l>y||tree[root].r<x) return 0;//不包含是要闹哪样
	if(x<=tree[root].l&&y>=tree[root].r) return tree[root].s;//包含,直接输出
	else return getsum(tree[root].lchild,x,y)+getsum(tree[root].rchild,x,y);//两边查
}
int main(){
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	build(tot,1,n);
	cout<<endl;
	int m;
	scanf("%d",&m);
	string s;
	int k,x,lnow,rnow;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="ADD"){
			scanf("%d%d",&k,&x);//d[k]+=x;
			d[k]+=x;
			add(0,k,x);
		}
		else{
			scanf("%d%d",&lnow,&rnow);//区间和[s,t]
			printf("%d\n",getsum(0,lnow,rnow));
		}
	}
	return 0;
}