AcWing 1267. 清点人数 (树状数组练习题)
原题链接
简单
作者:
@-_-@
,
2024-04-04 21:01:07
,
所有人可见
,
阅读 8
树状数组 O(nlogn)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500010;
int n, k;
int tr[N];
int lowbit(int x)
{
return x & -x;
}
int add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int ask(int x)
{
int sum = 0;
for (int i = x; i; i -= lowbit(i)) sum += tr[i];
return sum;
}
int main()
{
scanf("%d%d", &n, &k);
while (k --)
{
char op;
scanf("%s", &op);
if (op == 'A')
{
int m;
scanf("%d", &m);
printf("%d\n", ask(m));
}
else if (op == 'B')
{
int m, p;
scanf("%d%d", &m, &p);
add(m, p);
}
else
{
int m, p;
scanf("%d%d", &m, &p);
add(m, -p);
}
}
return 0;
}