题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
线段树模版
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node{
int left,right,sum;
struct node *l,*r;
}*Tree,Node;
int map[50008],num[50008];
Tree root;
Tree NEW()
{
Tree p;
p=(Tree)malloc(sizeof(Node));
p->l=NULL;p->r=NULL;
p->left=0;p->right=0;p->sum=0;
return p;
}
void Build(int l,int r,Tree p)
{
if(l==r)return;
int mid=(l+r)>>1;
Tree s,e;
s=NEW();
p->l=s;
s->sum=num[mid]-num[l-1];
s->left=l;
s->right=mid;
Build(l,mid,p->l);
e=NEW();
p->r=e;
e->sum=num[r]-num[mid];
e->left=mid+1;e->right=r;
Build(mid+1,r,p->r);
}
int Query(int a,int b,Tree p)
{
if(a==p->left && b==p->right)return p->sum;
int mid=(p->left+p->right)/2;
if(b<=mid)
return Query(a,b,p->l);
else if(a>=mid+1)
return Query(a,b,p->r);
else return Query(a,mid,p->l) + Query(mid+1,b,p->r);
}
void Add(int a,int b,Tree p)
{
if(p->left==a && p->right==a){
p->sum+=b;return;}
if(p->left<=a && p->right>=a)
{
p->sum+=b;
Add(a,b,p->l);
Add(a,b,p->r);
}
}
int main()
{
int ncase,i,n,T;
int a,b;
char str[10];
scanf("%d",&ncase);
for(T=1;T<=ncase;T++)
{
root=NEW();
scanf("%d",&n);
num[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&map[i]);
num[i]=num[i-1]+map[i];
}
root->left=1;root->right=n;root->sum=num[n];
Build(1,n,root);
printf("Case %d:\n",T);
while(scanf("%s",str),strcmp(str,"End"))
{
scanf("%d%d",&a,&b);
if(strcmp(str,"Query")==0)
printf("%d\n",Query(a,b,root));
else if(strcmp(str,"Add")==0)
Add(a,b,root);
else
Add(a,-b,root);
}
}
return 0;
}