http://poj.org/problem?id=1195

題意：給出一個矩陣，給某個格子加/減一個數(shù)，就某個子矩陣的和，1024*1024的范圍，二維的樹狀數(shù)組

子矩陣(x1,y1,x2,y2)（左下角的點和右上角的點）的和ans=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<string> #define nMAX 1050 using namespace std; int c[nMAX][nMAX],n; int lowbit(int x) {return x&(-x); } void add(int i,int j,int w) {int temp;while(i<=n){temp=j;while(temp<=n){c[i][temp]+=w;temp+=lowbit(temp);}i+=lowbit(i);} } int sum(int i,int j)//與一維的稍有不同 {int ans=0,temp;while(i>=1){temp=j;while(temp>=1){ans+=c[i][temp];temp-=lowbit(temp);}i-=lowbit(i);}return ans; } int main() {int i,j,k,f,commend;while(~scanf("%d",&commend)){if(commend==3)break;if(commend==0){scanf("%d",&n);memset(c,0,sizeof(c));}if(commend==1){scanf("%d%d%d",&i,&j,&k);//下表必須從1,1開始，因為lowbit(0)=0死循環(huán)add(i+1,j+1,k);}if(commend==2){scanf("%d%d%d%d",&i,&j,&k,&f);i++,j++,k++,f++;int ans=sum(k,f)-sum(i-1,f)-sum(k,j-1)+sum(i-1,j-1);printf("%d\n",ans);}}return 0; }

　　

轉載于:https://www.cnblogs.com/sdau10kuaile/archive/2012/08/17/2644700.html

總結

以上是生活随笔為你收集整理的POJ 1195 Mobile phones(裸的二维树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。