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
<span style="font-size:14px;">#include<cstdio>
#define maxn 55000
using namespace std;
int a[maxn];
struct seg_tree
{
int a,b; //a为左端点 b为右端点
int total; //[a,b]区间内的人数
}s_tree[maxn*4]; //开一个 maxn*4的结构数组
void build(int x,int y,int k) //在tree[k]位置建立线段[x,y]
{
int mid=(x+y)/2,i;
s_tree[k].a=x; s_tree[k].b=y; //左右端点
s_tree[k].total=0; //初始化区间人数为0
for(i=x;i<=y;i++) s_tree[k].total+=a[i];
if(y-x>=1)
{
build(x,mid,k*2+1); //在左子树tree[2*k+1]上建立线段[x,mid]
build(mid+1,y,k*2+2); //在右子树tree[2*k+2]上建立线段[mid+1,y]
}
}
int Query(int x,int y,int k)
{
//[x,y]完全覆盖结点k
if(x<=s_tree[k].a&&y>=s_tree[k].b) return s_tree[k].total;
int mid=(s_tree[k].a+s_tree[k].b)/2,ret;
if(x<=mid) //[x,y]与左子树有交点
{
if(y>=mid+1) ret=Query(x,mid,k*2+1)+Query(mid+1,y,k*2+2); //[x,y]右左子树有交点
else ret=Query(x,y,k*2+1); //[x,y]只与左子树有交点
}
else ret=Query(x,y,k*2+2); //[x,y]只与右子树有交点
return ret;
}
void Add(int x,int k,int p)
{
if(x>=s_tree[k].a&&x<=s_tree[k].b) s_tree[k].total+=p;
else return;
Add(x,k*2+1,p);
Add(x,k*2+2,p);
}
int main()
{
//freopen("a.in","r",stdin);
int T,i;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
printf("Case %d:\n",i);
int N,i,j;
char cmd[10];
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%d",&a[i]);
build(1,N,0);
while(scanf("%s",&cmd))
{
if(cmd[0]=='E') break;
scanf("%d %d",&i,&j);
if(cmd[0]=='A') Add(i,0,j);
else if(cmd[0]=='S') Add(i,0,-1*j);
//else printf("区间[%d %d]的人数为:%d\n",i,j,Query(i,j,0));
else printf("%d\n",Query(i,j,0));
}
}
return 0;
}</span>
原文：http://blog.csdn.net/rechard_chen/article/details/42271277