POJ 1195 Mobile phones【二维树状数组】-白红宇

POJ 1195 Mobile phones【二维树状数组】

阅读量：4308 次

发布时间：2019-06-06

本文共 1427 字，大约阅读时间需要 4 分钟。

题意：基础的二维数组，注意 0 + lowbit(0)会陷入无限循环-----

之前做一道一维的一直tle,就是因为这个--------------------------

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std;12 13 typedef long long LL;14 const int INF = (1<<30)-1;15 const int mod=1000000007;16 const int maxn=1000005;17 18 int c[1055][1055];19 int n;20 21 int lowbit(int x){ return x & (-x);}22 23 int sum(int x,int y){24 int ret = 0,y1;25 while(x > 0){26 y1 = y;27 while( y1 > 0){28 ret += c[x][y1];y1 -= lowbit(y1);29 }30 x-=lowbit(x);31 }32 return ret;33 }34 35 void add(int x,int y,int d){36 int y1;37 while(x <= n){38 y1 = y;39 while(y1 <= n){40 c[x][y1] += d; y1 += lowbit(y1);41 }42 x += lowbit(x);43 }44 }45 46 int main(){47 int cmd;48 while(scanf("%d %d",&cmd,&n) != EOF){49 memset(c,0,sizeof(c));50 while(scanf("%d",&cmd) != EOF && cmd != 3){51 if(cmd == 1){52 int x,y,d;53 scanf("%d %d %d",&x,&y,&d);x++;y++;54 add(x,y,d);55 }56 else{57 int x,y,xx,yy;58 int ret = 0;59 scanf("%d %d %d %d",&x,&y,&xx,&yy);60 x++;y++;xx++;yy++;61 ret = sum(xx,yy) - sum(x-1,yy) - sum(xx,y-1) + sum(x-1,y-1);62 printf("%d\n",ret);63 }64 }65 }66 return 0;67 }