hdoj 1166 敌兵布阵 (线段树裸题)

http://acm.hdu.edu.cn/showproblem.php?pid=1166
题意：维护一个序列进行下列操作：

线段树裸题，维护区间和，点修改，区间查询。

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;
const int N=50010;
int a[N],T,n,x,y;
char s[10];
struct Seg{int v;Seg *ls,*rs;
}*root;
//建树
void build(Seg* &p,int l,int r)
{p=new Seg();p->v=0;if(l==r){p->v=a[l];return ;}int mid=(l+r)/2;build(p->ls,l,mid);build(p->rs,mid+1,r);p->v=p->ls->v+p->rs->v;
}
//单点修改a[k]+=val
void modify(Seg* &p,int l,int r,int k,int val)
{if(k<l||k>r) return ;else{p->v+=val;if(l==r) return ;int mid=(l+r)/2;modify(p->ls,l,mid,k,val);modify(p->rs,mid+1,r,k,val);}
}
//区间查询[L,R]
int query(Seg* &p,int l,int r,int L,int R)
{if(l>R||r<L) return 0;else if(L<=l&&r<=R) return p->v;else{int mid=(l+r)/2;return query(p->ls,l,mid,L,R)+query(p->rs,mid+1,r,L,R);}
}
int main()
{scanf("%d",&T);for(int cas=1;cas<=T;cas++){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(root,1,n);printf("Case %d:\n",cas);while(1){scanf("%s",s);if(s[0]=='E') break;scanf("%d%d",&x,&y);if(s[0]=='A')modify(root,1,n,x,y);if(s[0]=='S')modify(root,1,n,x,-y);if(s[0]=='Q')printf("%d\n",query(root,1,n,x,y));}}return 0;
}