记录编号	142257	评测结果	AAAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	chs	是否通过	通过
代码语言	C++	运行时间	1.554 s
提交时间	2014-12-06 21:21:06	内存使用	4.89 MiB

#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
//==============================//
#define maxn 100000
//==============================//
//=============tree=============//
const int root=1;
struct node
{
	int s;
	int L,R;
}tree[4*maxn+1];
void construct(int x,int y,int k)
{
	tree[k].s=0;
	tree[k].L=x;
	tree[k].R=y;
	if(x==y) return ;
	int m=(x+y)>>1;
	construct(x,m,k<<1);
	construct(m+1,y,(k<<1)+1);
}
void edit(int k,int pos,int d)
{
	if(tree[k].L==tree[k].R)
	{
		tree[k].s+=d;
		return ;
	}
	int m=(tree[k].L+tree[k].R)>>1;
	if(pos<=m) edit(k<<1,pos,d);
	if(pos>=m+1) edit((k<<1)+1,pos,d);
	tree[k].s=(tree[k<<1].s+tree[(k<<1)+1].s);
}
int sum(int s,int t,int k)
{
	//cout<<s<<" "<<t<<" "<<tree[k].L<<" "<<tree[k].R<<" "<<endl;
	if(s==tree[k].L&&t==tree[k].R) return tree[k].s;
	if(tree[k].L==tree[k].R) return tree[k].s;
	int tot=0;
	int m=(tree[k].L+tree[k].R)>>1;
	if(t<=m) return sum(s,t,2*k);
	if(s>=m+1) return sum(s,t,2*k+1);
	return sum(s,m,2*k)+sum(m+1,t,2*k+1);
}
//==============================//
int n,m;
//==============================//
void check()
{
	for(int k=1;k<=7;k++) cout<<tree[k].L<<" "<<tree[k].R<<" "<<tree[k].s<<endl;
	cout<<endl;
}
void init()
{
	cin>>n;
	if(n==0) return ;
	construct(1,n,root);
	int d;
	for(int i=1;i<=n;i++)
	{
		cin>>d;
		edit(root,i,d);
	}
	cin>>m;
}
void print()
{
	if(n==0) return ;
	string s;
	int a,b;
	while(m--)
	{
		cin>>s>>a>>b;
		//cout<<s<<" "<<a<<" "<<b<<endl;
		if(s=="ADD") edit(root,a,b);
		if(s=="SUM") cout<<sum(a,b,root)<<endl;
		//check();
	}
}
int main()
{
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	init();
	print();
	return 0;
}