HDU1166树状数组裸题
1.题意就不在介绍,只放一张图和AC代码,因为这个东西的思想和线段树有异曲同工之妙,所以不是太懂的只需要看一下线段树是怎么实现的。
#include"stdafx.h"
#include <iostream>
#include <algorithm>
#include<string>
using namespace std;
const int maxx = 50010;
int c[maxx];
int n;
//这个lowerbit的解释可以有很多种,我们就采用一种简单的解释方法
//lowerbit函数就是为了找出这样一个数:假设这个数的二进制数据是10000,那么我们要找的就是pow(2,4).
//因为从低位到高位连续有4个0,所以就是2的4次幂。没错,连续有几个0就是2的几次幂。
int lowbit(int k) { return k & (-k); }
//这是在点更新
void add(int x, int y) {
while (x <= n) {
c[x] += y;
x += lowbit(x);
}
return;
}
//这是在预处理前缀和
int sum(int x) {
int sum = 0;
while (x > 0) {
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int main() {
int T, x, y, xu = 1;
string s;
cin >> T;
while (T--) {
memset(c, 0, sizeof(int)*maxx);
printf("Case %d:\n", xu++);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
add(i, x);
}
while (1) {
cin >> s;
if (s[0] == 'E') break;
else if (s[0] == 'A') {
cin >> x >> y;
add(x, y);
}
else if (s[0] == 'S') {
cin >> x >> y;
add(x, -y);
}
else if (s[0] == 'Q') {
cin >> x >> y;
cout << sum(y) - sum(x - 1) << endl;
}
}
}
return 0;
}