这是我写的第一个线段树题，这种题过程很抽象，代码不容易理解，整整写了三小时，修BUG修了很久，不过还好过了。
思路：这个有点像二分的思想，根节点就是全部兵营，下来的第一个左子结点是全部兵的左半，右子节点是剩下的一半，经过重重递归二分，递归的边界就是只剩一个元素，即左子节点等于右子节点，这样，线段树就构造完成了，增删查改都是通过遍历来找到特定区间或元素，再改变它的值。
下面附上AC代码：
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
const int N=5e4+10;
int str[N];
int m,n;
int s;struct tree
{int sum,l,r;
}node[N*4];void build_tree(int ans,int ll,int rr)//ans是根节点!!!
{if( ll == rr ){node[ans].l = node[ans].r = ll;node[ans].sum = str [ll];return ;}node[ans].l = ll;node[ans].r = rr;//printf("Z");int mid = (ll + rr )>>1;//printf("C");build_tree(ans<<1,ll,mid);build_tree(ans<<1|1,mid+1,rr);node[ans].sum = node [ans<<1].sum + node[ans<<1|1].sum ;
}void update(int ans,int pos,int value)//更新数值
{if(node[ans].l == pos && node[ans].r == pos){node[ans].sum += value ;return ;}int mid = (node[ans].l+node[ans].r)>>1;if(pos <= mid){update(ans<<1,pos,value);}else{update(ans<<1|1,pos,value);}node[ans].sum = node[ans<<1].sum + node[ans<<1|1].sum ;
}void query(int ans,int ll,int rr)
{int mid = (node[ans].l+node[ans].r)>>1;if(node[ans].l == ll && node[ans].r == rr){s += node[ans].sum;return ;}else if( ll > mid ){query(ans<<1|1,ll,rr);}else if( rr <= mid ){query(ans<<1,ll,rr);}else{query(ans<<1,ll,mid);query(ans<<1|1,mid+1,rr);}
}int main()
{int t,x,y;int cas=0;char ch[10];scanf("%d",&t);while(t--){scanf("%d",&m);for(int i=1;i<=m;i++)scanf("%d",&str[i]);printf("Case %d:\n",++cas);build_tree(1,1,m);while(~scanf("%s",ch),ch[0]!='E'){scanf("%d%d",&x,&y);if(ch[0] == 'A'){update(1,x,y);//printf("A");}else if(ch[0] == 'S'){// printf("S");update(1,x,-y);}else if(ch[0] == 'Q'){s=0;//printf("Q");query(1,x,y);printf("%d\n",s);}}}return 0;
}