卢俊达

题目大意：

给出一个序列和四种操作：
(1) Add i j ，i和j为正整数，第i个元素增加j（j不超过30）；
(2) Sub i j ，i和j为正整数，第i个元素减少j（j不超过30）；
(3) Query i j ，i和j为正整数，i<=j，表示询问第i到第j个元素的和； (4) End 表示结束，这条命令在每组数据最后出现； 执行操作并对(3)进行答复。

思路：

树状数组、线段树的模板题。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define datasize 50000
int c[datasize+1],n;
int lowbit(int x)
{
	return x&-x;
}
int sum(int end)
//求取序列1至end的和。 
{
	int s=0;
	while(end>0)
	{
		s+=c[end];
		end-=lowbit(end);
	}
	return s;
}
void modify(int pos,int val)
//在序列第pos位上加上val。 
{
	while(pos<=n)
	{
		c[pos]+=val;
		pos+=lowbit(pos);
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		printf("Case %d:\n",i);
		memset(c,0,sizeof(c));
		scanf("%d",&n);
		for(int j=1,t;j<=n;j++)
		{
			scanf("%d",&t);
			modify(j,t);
			//更新操作即是建树操作。 
		}
		char op[10];
		while(scanf("%s",op)&&strcmp(op,"End"))
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(!strcmp(op,"Query"))
				printf("%d\n",sum(b)-sum(a-1));
				//[a,b]的和即是[1,b]的和减去[1,a-1]的和。 
			else if(!strcmp(op,"Add"))
				modify(a,b);
			else if(!strcmp(op,"Sub"))
				modify(a,-b);
			else
				break;
		}
	}
}