二维树状数组

POJ 1195 Mobile phones
裸的二维树状数组，贴个模板~
 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<vector>
12 #include<cstdlib>
13 #include<cstring>
14 #include<complex>
15 #include<utility>    //pair
16 #include<iostream>
17 #include<algorithm>
18 #define MAXN 1105
19 #define INF 0x3f3f3f3f
20 #define LL long long
21 #define DBL double
22 #define EPS 1e-6
23 #define PI acos(-1.0)
24 #define Test() cout<<"Test"<<endl;
25 #define Debug(a) cout<<#a<<" = "<<a<<endl;
26 #define Debug2(a,b) cout<<#a<<" = "<<a<<" , "<<#b<<" = "<<b<<endl;
27 using namespace std;
28 
29 int cmd, n;
30 int c[MAXN][MAXN];
31 
32 int lowbit(int x){
33     return x&(-x);
34 }
35 void add(int x, int y, int val){
36     for(int i=x; i<=n; i+=lowbit(i))
37       for(int j=y; j<=n; j+=lowbit(j))
38          c[i][j]+=val;
39 }
40 int sum(int x, int y){
41     //if(x<=0||y<=0) return 0;
42     int s=0;
43     for(int i=x; i>0; i-=lowbit(i))
44       for(int j=y; j>0; j-=lowbit(j))
45          s+=c[i][j];
46     return s;
47 }
48 
49 int main()                //2维树状数组
50 {
51     cin>>cmd;
52     while(cmd!=3){
53         if(cmd == 0){
54             cin>>n>>cmd;
55             memset(c, 0, sizeof(c));    //init~~
56             continue;
57         }
58         while(cmd!=3){
59             if(cmd==1){
60                 int x, y, a;
61                 scanf("%d%d%d", &x, &y, &a);
62                 x++, y++;
63                 add(x, y, a);
64             }else{
65                 int l, b, r, t;
66                 scanf("%d%d%d%d", &l, &b, &r, &t);
67                 l++, b++, r++, t++;
68                 printf("%d
", sum(r, t)+sum(l-1, b-1)-sum(r, b-1)-sum(l-1, t));
69             }
70             scanf("%d", &cmd);
71         }
72     }
73     return 0;
74 }
View Code