求區間的和，並可更新，線段樹
[cpp]
#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;
} www.2cto.com
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;
}
作者：Cambridgeacm
