Light oj 1112 - Curious Robin Hood(树状数组)

//LA 1112 - Curious Robin Hood(树状数组)
//2013-04-13-08.22
#include <stdio.h>
#include <string.h>
const int maxn = 100010;

int a[maxn], b[maxn];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void update(int x, int v)
{
    while (x <= n)
    {
        a[x] += v;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x)
    {
        sum += a[x];
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    int t, m;
    scanf("%d",&t);
    for (int k = 1; k <= t; k++)
    {
        scanf("%d %d",&n, &m);
        memset(a, 0 ,sizeof(a));
        for (int i = 1; i <= n; i++)
        {
            scanf("%d",&b[i]);
            update(i, b[i]);
        }
        int op, i, v, j;
        printf("Case %d:\n",k);
        while (m--)
        {
            scanf("%d",&op);
            if (op == 1)
            {
                scanf("%d",&i);
                printf("%d\n",b[i+1]);
                update(i+1, -b[i+1]);
                b[i+1] = 0;
            }
            else if (op == 2)
            {
                scanf("%d %d",&i, &v);
                update(i+1, v);
                b[i+1] += v;
            }
            else
            {
                scanf("%d %d",&i,&j);
                printf("%d\n",getsum(j+1) - getsum(i));
            }
        }
    }
    return 0;
}