首页 > 代码库 > 二维树状数组

二维树状数组

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\n",gx.query(l+1,b+1,r+1,t+1));43         }44     }45     return 0;46 }
View Code

 

 

 

 

end