C++-hdu1166-敌兵布阵[数据结构][树状数组]

单点修改+区间查询=树状数组

空间复杂度O(n)

时间复杂度O(mlogn)

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=50001;
int a[MAXN],n,t=1,T;char s[10];
int lb(int i){return i&-i;}//lowbit
void init(){memset(a,0,sizeof(a));}
void add(int i,int v){for(;i<=n;a[i]+=v,i+=lb(i));}
int sum(int i){int ans=0;for(;i;ans+=a[i],i-=lb(i));return ans;}
int query(int i,int j){return sum(j)-sum(i-1);}
int main() {
    for(scanf("%d",&T);t<=T;t++){
        scanf("%d",&n),init();
        for(int i=1,v;i<=n;i++)scanf("%d",&v),add(i,v);
        printf("Case %d:\n",t);
        for(int x,y;scanf("%s",s)&&s[0]!=‘E‘;){
            scanf("%d%d",&x,&y);
            if(s[0]==‘A‘)add(x,y);
            else if(s[0]==‘S‘)add(x,-y);
            else printf("%d\n",query(x,y));
        }
    }
    return 0;
}