admin管理员组文章数量:1612097
题意:
有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;
}
版权声明:本文标题:Light oj 1112 - Curious Robin Hood(树状数组) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728631222a1167108.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论