HDU-1166-敌兵布阵

HDU-1166-敌兵布阵

http://acm.hdu.edu.cn/showproblem.php?pid=1166

求区间的和，并可更新，线段树

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 50005
int num[N];
struct cam
{
	int x;  //起点
	int y;  //终点
	int sum; //总数
}list[N*4];
void build(int k,int x,int y)
{
	int mid;
	list[k].x=x;
	list[k].y=y;
	if(list[k].x==list[k].y)
	{
		list[k].sum=num[x];
		return;
	}
	mid=(x+y)/2;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
	list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
int find(int k,int x,int y)
{
	int mid;
	if(list[k].x==x&&list[k].y==y)
	return list[k].sum;
	mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	return find(k<<1|1,x,y);
	else if(y<=mid)
	return find(k<<1,x,y);
	return find(k<<1,x,mid)+find(k<<1|1,mid+1,y);
}
void update(int k,int x,int y)
{
	int mid;
	if(list[k].x==x&&list[k].y==x)
	{
		list[k].sum=y;
		return;
	}
	mid=(list[k].x+list[k].y)/2;
	if(x<=mid)
	update(k<<1,x,y);
	else
	update(k<<1|1,x,y);
	list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
int main()
{
	int k,t,a,b;
	int i,n,m;
	char str[10];
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		scanf("%d",&num[i]);
		build(1,1,n);
		printf("Case %d:\n",k);
		while(scanf("%s",str),strcmp(str,"End"))
		{
			scanf("%d%d",&a,&b);
			if(strcmp(str,"Query")==0)
			printf("%d\n",find(1,a,b));
			else if(strcmp(str,"Add")==0)
			{
				num[a]+=b;
				m=num[a];
				update(1,a,m);
			}
			else if(strcmp(str,"Sub")==0)
			{
				num[a]-=b;
				m=num[a];
				update(1,a,m);
			}
		}
	}
	return 0;
}