hdoj 1166 敌兵布阵(树状数组)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

思路分析：该问题为动态连续和查询问题，使用数组数组可以解决；也可使用线段树解决该问题；

 

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAX_N = 50000 + 10;
int c[MAX_N];
inline int Lowbit(int x) { return x & -x; }
inline int Sum(int x)
{
int ret = 0;
while (x) {
ret += c[x];
x -= Lowbit(x);
}
return ret;
}
inline void Add(int x, int d, int n)
{
while (x <= n) {
c[x] += d;
x += Lowbit(x);
}
}
int main()
{
int a = 0, b = 0, ans = 0, temp = 0;
int test_case = 0, case_id = 0, n = 0;
char command[10];
scanf("%d", &test_case);
while (test_case--) {
scanf("%d", &n);
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; ++ i) {
scanf("%d", &temp);
Add(i, temp, n);
}
printf("Case %d:n", ++case_id);
while(scanf("%s", command) != EOF && command[0] != 'E') {
scanf("%d %d", &a, &b);
if (command[0] == 'Q') {
ans = Sum(b) - Sum(a - 1);
printf("%dn", ans);
} else if (command[0] == 'A') {
Add(a, b, n);
} else {
Add(a, -b, n);
}
}
}
return 0;
}