小记:这题基本上算是一维树状数组的最简单的应用了。一维数组最简单的应用就是:单点更新,区间求和。
这题只要理解了树状数组,不懂的可以去看看我的树状数组 详解,就能做出来,题意很清楚。
下面附上代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define N 50001 int C[N]; int n; int Lowbit(int x){ return x&(x^(x-1)); } void add(int pos,int num) { while(pos <= n) { C[pos] += num; pos += Lowbit(pos); } } int Sum(int end) { int sum = 0; while(end > 0) { sum += C[end]; end -= Lowbit(end); } return sum; } int main() { int T, s, t, k; char str[10]; scanf("%d",&T); for(int i = 1; i <= T; i++) { scanf("%d",&n); memset(C,0,sizeof(C)); for(int j = 1; j <= n; j ++) { scanf("%d",&k); add(j,k); } printf("Case %d:\n",i); while(1) { scanf("%s",str); if(str[0] == 'E')break; scanf("%d%d",&s,&t); switch(str[0]) { case 'Q': printf("%d\n",Sum(t) - Sum(s-1)); break; case 'A': add(s,t); break; case 'S': add(s,-t); break; } } } return 0; }