[树状数组]hdoj 1166

题意

    http://acm.hdu.edu.cn/showproblem.php?pid=1166

思路

   用线段树做过，这次换用树状数组来写。http://www.cnblogs.com/zhangshu/archive/2011/08/16/2141396.html这一篇树状数组的介绍真的很好。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define lowbit(x) (x&(-x))
const int nMax = 50050;
int n, num[nMax];

void add(int loc, int val){
    while(loc <= n){
        num[loc] += val;
        loc += lowbit(loc);
    }
}

int sum(int loc){
    int res = 0;
    while(loc >= 1){
        res += num[loc];
        loc -= lowbit(loc);
    }
    return res;
}

int main(){
    int tcas,i,a,b,v;
    char sss[10];
    scanf("%d",&tcas);
    for(int tt = 1; tt <= tcas; tt ++){
        scanf("%d",&n);
        memset(num, 0, sizeof(num));
        for(i = 1; i <= n; i++){
            scanf("%d",&a);
            add(i, a);
        }
        printf("Case %d:\n",tt);
        while(scanf("%s",sss)&&sss[0]!='E'){
            scanf("%d%d",&a,&b);
            if(sss[0] == 'A'){
                add(a, b);
            }else{
                if(sss[0] == 'S'){
                    add(a, -b);
                }else{
                    v = sum(b) - sum(a - 1);
                    printf("%d\n",v);
                }
            }
        }
    }
    return 0;
}