セグメントツリーテンプレートコード
5120 ワード
# include ///
using namespace std;
# define MAXN 50005
int data[MAXN];
int sum[MAXN*4];
int suy, L, R;
void build(int root, int l, int r)
{
if(l==r)
sum[root]=data[l];
else
{
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
sum[root]=sum[root*2]+sum[root*2+1];
}
}
void Query(int root, int l, int r)
{
if(L<=l&&R>=r)
{
suy+=sum[root];
}
else
{
int mid=(l+r)/2;
if(mid>=L)
Query(root*2,l,mid);
if(mid2+1,mid+1,r);
}
}
void Updata(int root, int l, int r)
{
if(l==r)
{
sum[root]+=R;
}
else
{
int mid=(l+r)/2;
if(L<=mid)
{
Updata(root*2,l,mid);
}
else
{
Updata(root*2+1,mid+1,r);
}
sum[root]=sum[root*2]+sum[root*2+1];
}
}
int main()
{
int T;
cin>>T;
for(int t=1; t<=T; t++)
{
int N;
cin>>N;
for(int i=1; i<=N; i++)
scanf("%d",&data[i]);
build(1,1,N);
cout<<"Case "<':'<char ans[10];
while(~scanf("%s",ans)&&(ans[0]!='E'))
{
scanf("%d%d",&L,&R);
if(ans[0]=='A')
Updata(1,1,N);
else if(ans[0]=='S')
{
R=-R;
Updata(1,1,N);
}
else if(ans[0]=='Q')
{
suy=0;
Query(1,1,N);
cout<