敌兵布阵

                                                        Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

                                                                            Total Submission(s): 59474    Accepted Submission(s): 25122

1

10

1 2 3 4 5 6 7 8 9 10

Query 1 3

Add 3 6

Query 2 7

Sub 10 2

Add 6 3

Query 3 10

End 

Case 1:

6

33

59

题目链接：http://acm.hdu.edu.cn/showproblem.php?

pid=1166

解题思路：裸的线段树单点更新。

代码例如以下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

using namespace std;

int const maxn= 50005;

int tr[4*maxn];

void Build(int l,int r,int root)  //建树

{

	if(l==r)

	{

		scanf("%d",&tr[root]);

		return ;

	}

	int mid=(l+r)/2;

	Build(l,mid,root*2);

	Build(mid+1,r,root*2+1);

	tr[root]=tr[root*2]+tr[root*2+1];

}

int Query(int l,int r,int a,int b,int root)  //查询

{

	if(l>=a&&r<=b)

		return tr[root];

	int mid=(l+r)/2,sum=0;

	if(a<=mid)

		sum+=Query(l,mid,a,b,root*2);

	if(b>mid)

		sum+=Query(mid+1,r,a,b,root*2+1);

	return sum;

}

void Change(int l,int r,int x,int v,int root)  //更新

{

	if(l==r)

	{

		if(l==x)

			tr[root]+=v;

		return;

	}

	int mid=(l+r)/2;

	if(x<=mid)

		Change(l,mid,x,v,root*2);

	else

		Change(mid+1,r,x,v,root*2+1);

	tr[root]=tr[root*2]+tr[root*2+1];

}

int main(void)

{

	int t;

	string s;

	scanf("%d",&t);

	for(int ca=1;ca<=t;ca++)

	{

		int n,a,b;

		scanf("%d",&n);

		Build(1,n,1);

		printf("Case %d:\n",ca );

		while(cin>>s)

		{

			if(s=="End")

				break;

			scanf("%d%d",&a,&b);

			if(s[0]=='Q')

				printf("%d\n",Query(1,n,a,b,1));

			else if(s[0]=='S')

				Change(1,n,a,-b,1);

			else

				Change(1,n,a,b,1);

		}

	}

}