二维树状数组

Mobile phones http://poj.org/problem?id=1195
 1 #include<cstdio>
 2 #include<cstring>
 3 #define mt(a,b) memset(a,b,sizeof(a))
 4 const int M=1030;
 5 class Two_Tree_Array {  // 二维树状数组
 6     typedef int typev;
 7     typev c[M][M];
 8 public:
 9     void init() {
10         mt(c,0);
11     }
12     int lowb(int t) {
13         return t&(-t);
14     }
15     void add(int x,int y,typev v) {
16         for(int i=x; i<M; i+=lowb(i))
17             for(int j=y; j<M; c[i][j]+=v,j+=lowb(j));
18     }
19     typev sum(int x,int y) {
20         typev res=0;
21         for(int i=x; i>0; i-=lowb(i))
22             for(int j=y; j>0; res+=c[i][j],j-=lowb(j));
23         return res;
24     }
25     typev query(int x1,int y1,int x2,int y2) {
26         return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
27     }
28 } gx;
29 int main(){
30     int op,l,b,r,t,n;
31     while(~scanf("%d",&op),op!=3){
32         if(!op){
33             scanf("%d",&n);
34             gx.init();
35         }
36         else if(op&1){
37             scanf("%d%d%d",&l,&b,&op);
38             gx.add(l+1,b+1,op);
39         }
40         else{
41             scanf("%d%d%d%d",&l,&b,&r,&t);
42             printf("%d
",gx.query(l+1,b+1,r+1,t+1));
43         }
44     }
45     return 0;
46 }
View Code
end