题意：
给定n个兵营的士兵初始值， 然后有最多40000个操作；
操作一共有两种， 一个是查询给定[a,b]区间兵营的士兵总和。
另一个是增加/减少指定兵营的士兵数目。
输出每次查询的值。
分析：
线段树单点更新模板
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
struct{
int l, r, sum;
}tree[maxn*];//起码要*4
int a[maxn];
int n;
void build(int index, int l , int r){
tree[index].l = l, tree[index].r = r;
if( l == r){
tree[index].sum = a[l];//递归建树，当l=r就是叶子节点没办法再分，直接赋值
return;
}
int mid = (l+r) / ;
build(index * , l, mid);
build(index * + , mid + , r);
tree[index].sum = tree[index * ].sum + tree[index* + ].sum;//不是叶子节点， 总和等于它儿子的总和
} void update(int index, int a, int val){ //修改总和的
if(tree[index].l == a && tree[index].r == a){
tree[index].sum += val;//找到该点，直接更改
return;
}
int mid = (tree[index].l + tree[index].r) / ; if(a <= mid)
update(index * , a , val);
else
update(index * + , a, val); tree[index].sum += val;//路径上的点都要更改。
} int query(int index , int ql, int qr){ if(tree[index].l == ql && tree[index].r == qr){
return tree[index].sum;
} int mid = (tree[index].l + tree[index].r) / ;
if(qr <= mid) //查询区间只在这个的左子树
return query(index * , ql, qr);
if(ql > mid) //只在右子树
return query(index * + , ql, qr); return query(index * , ql, mid) + query(index * + , mid + , qr);//左右子树都有的话， 拆分查询区间
} int main(){
int T;
scanf("%d", &T);
int kase = ;
while(T--){
printf("Case %d:\n", kase++);
scanf("%d", &n);
for(int i = ; i <= n; i++){
scanf("%d", &a[i]);
}
build(,,n);
char cho[];
while(scanf("%s",cho) && cho[] != 'E'){
int x, y;
scanf("%d %d", &x, &y);
if(cho[] == 'Q'){
printf("%d\n", query(,x,y));
}
else if(cho[] == 'A'){
update(,x,y);
}
else update(,x,-y);
}
}
return ;
}