题解：
更新是线段树的单点更新，简单一点。
有50000个阵营，40000查询，用普通数组肯定超时。区间求和和区间查询问题用线段树最好不过了。
先说说什么是线段树。
区间[1,10]用树的方法存起来，怎么存呢，来看下图：
线段树结构主要用于区间查询和更新。时间复杂度为lgN。虽然空间大了但时间快了。对于数据到达 亿 级别的，效果尤为显著。
知道了线段树的结构，那么怎么用代码实现建树，查询以及更新呢..看代码。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring> //杭电上 如果用c++编译器则改成incluce<string> ，c++编译器不支持cstring不知道为啥。 using namespace std; //这道题建议用G++编译器提交 const int MAX=50001; typedef struct node //定义树节点
{
node(){l=0,r=0,data=0;} //构造函数
int l,r; //区间[l,r]
int data; //数据，这里指区间[l,r]的和
}TreeNode; TreeNode treeNode[MAX<<4];
int a[MAX]; void update(int p) //向上更新
{
treeNode[p].data=treeNode[p*2].data+treeNode[p*2+1].data;
} void buildTree(int p,int l,int r) //建树,p是节点编号，从1开始，l,r是区间
{
treeNode[p].l=l;
treeNode[p].r=r; if(l==r) //如果是叶子节点，则赋值 返回
{
treeNode[p].data=a[l];
return;
}
int mid=(l+r)>>1; //
buildTree(p<<1,l,mid); //递归地创建左子树和右子树 p<<1 <==> p*2
buildTree(p<<1|1,mid+1,r); // p<<1|1 <==> p*2+1
update(p); //回溯的时候更新data值
return;
} void add(int p,int k,int x) //添加方法，p节点编号（索引），k为要修改的区间[k,k]，x为要修改的值
{
if(treeNode[p].l==k&&treeNode[p].r==k) //如果找到区间[k,k]
{
treeNode[p].data+=x;
return;
}
int mid=(treeNode[p].l+treeNode[p].r)/2;
if(k<=mid) add(p<<1,k,x); //如果要修改的点在当前区间的左边，查找左子树
else add(p<<1|1,k,x); //如果要修改的点在当前区间的右边，在右子树里查找
update(p); //回溯的时候更新data信息
return;
} int query(int p,int l,int r) //p为节点编号，查询区间[l,r];
{
if(treeNode[p].l>=l&&treeNode[p].r<=r) //如果当前节点的区间在[l,r]内
{
return treeNode[p].data;
}
if(treeNode[p].l>r||treeNode[p].r<l) //如果当前区间和要查找的区间没有交集
{
return 0;
}
int sum=0;
sum+=query(p<<1,l,r); //查询左子树
sum+=query(p<<1|1,l,r); //查询右子树
return sum;
} int main()
{
int n,tt; //区间[1,n]，有tt组测试数据
//cin>>tt; //测试数据 输入就有 40000+，用cin就超时，scanf秒过，或者能用scanf的就用scanf
scanf("%d",&tt);
for(int t=1;t<=tt;t++)
{
//cin>>n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
//cin>>a[i];
scanf("%d",&a[i]);
}
buildTree(1,1,n); //建树，节点编号从1开始，区间[1,n] string op; //操作 printf("Case %d:\n",t); while(cin>>op) //string 类型只能用cin输入
{
if(op=="Query")
{
int a,b;
//cin>>a>>b;
scanf("%d%d",&a,&b);
//cout<<query(1,a,b)<<endl;
printf("%d\n",query(1,a,b));
continue;
}
if(op=="Add")
{
int a,b;
//cin>>a>>b;
scanf("%d%d",&a,&b);
add(1,a,b);
continue;
}
if(op=="Sub")
{
int a,b;
//cin>>a>>b;
scanf("%d%d",&a,&b);
add(1,a,-b);
continue;
}
if(op=="End")
{
break;
}
} }
return 0;
}