学步园

#include <stdio.h>
#include <string.h>
#define lowbit(x) (x&(-x))
#define M 50050
int ar[M],n;

void add (int u,int
w)    

{
    while (u
<= n)  
//从该结点到根结点都加上w
    {
       
ar[u] += w;
       
u += lowbit(u);  //找它的父亲结点
    }
}

int sum (int u)
{
    int ans =
0;
    while (u
> 0)  
//ar[1]~ar[u] 的和
       
ans += ar[u],u -= lowbit(u);
    return
ans;
}
int main ()
{
    int
a,t,w,count = 0;
    char
str[10];
    scanf
("%d",&t);
    while (t
--)
    {
       
scanf ("%d",&n);
       
memset (ar,0,sizeof(ar));
       
for (int i = 1;i <= n;i ++)
       
{
           
scanf ("%d",&w);
           
add(i,w);
       
}
        
printf ("Case %d:\n",++count);
       
while (scanf ("%s",str)&&str[0] !=
'E')
       
{
           
scanf ("%d%d",&a,&w);
           
if (str[0] == 'A')
               
add (a,w);
           
else if (str[0] == 'S')
               
add (a,-w);
           
else
               
printf ("%d\n",sum(w) - sum(a-1));
       
}
    }
    return
0;
}