题意:
有n个数,有m组操作,1 i表示将第i个数先输出,然后置0, 2 i v 表示给第i个数加上v, 3 i j 表示求i 到 j 的和,注意,这里数组是从0开始的,而我们构造的树状数组是从1
开始的,使用在程序中要进行一定的处理。
//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;
}