题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1166
题目大意:
维护动态的区间和,单点更新,就是模板题
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = + ;
typedef long long ll;
int tree[maxn];
int n;
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int d)
{
while(x <= n)
{
tree[x] += d;
x += lowbit(x);
}
}
ll sum(int x)
{
ll ret = ;
while(x > )//此处等于0会导致无限循环
{
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
int main()
{
int T, cases = ;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
memset(tree, , sizeof(tree));
int x, y;
for(int i = ; i <= n; i++)
{
scanf("%d", &x);
add(i, x);
}
char s[];
printf("Case %d:\n", ++cases);
while(scanf("%s", s) && s[] != 'E')
{
scanf("%d%d", &x, &y);
if(s[] == 'A')
{
add(x, y);
}
else if(s[] == 'S')
{
add(x, -y);
}
else if(s[] == 'Q')
{
ll ans = sum(y) - sum(x - );
printf("%lld\n", ans);
}
}
}
}