首页 > 代码库 > 二维树状数组
二维树状数组
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 }
end
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。