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

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

空间复杂度O(n)

时间复杂度O(mlogn)

 1 #include <set>
 2 #include <map>
 3 #include <cmath>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=50001;
13 int a[MAXN],n,t=1,T;char s[10];
14 int lb(int i){return i&-i;}//lowbit
15 void init(){memset(a,0,sizeof(a));}
16 void add(int i,int v){for(;i<=n;a[i]+=v,i+=lb(i));}
17 int sum(int i){int ans=0;for(;i;ans+=a[i],i-=lb(i));return ans;}
18 int query(int i,int j){return sum(j)-sum(i-1);}
19 int main() {
20     for(scanf("%d",&T);t<=T;t++){
21         scanf("%d",&n),init();
22         for(int i=1,v;i<=n;i++)scanf("%d",&v),add(i,v);
23         printf("Case %d:
",t);
24         for(int x,y;scanf("%s",s)&&s[0]!='E';){
25             scanf("%d%d",&x,&y);
26             if(s[0]=='A')add(x,y);
27             else if(s[0]=='S')add(x,-y);
28             else printf("%d
",query(x,y));
29         }
30     }
31     return 0;
32 }

~~Jason_liu O(∩_∩)O