HOJ 1640 Mobile Phone

題意：有一個n*n的矩陣，op==1時，在(x,y)增加值z，op==2時，求以(x1,y1)和(x2,y2)構成的矩陣的和。

思路：二維線段樹。

代碼：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N=1111;
 4 int c[N][N],n;
 5 int lowbit(int x)
 6 {
 7     return x&-x;
 8 }
 9 void add(int x,int y,int z)
10 {
11     for(int i=x;i<=n;i=(i|(i-1))+1)
12         for(int j=y;j<=n;j=(j|(j-1))+1)
13             c[i][j]+=z;
14 }
15 int q(int x,int y)
16 {
17     int sum=0;
18     for(int i=x;i;i=i&(i-1))
19         for(int j=y;j;j=j&(j-1))
20             sum+=c[i][j];
21     return sum;
22 }
23 int main()
24 {
25     int op,x,y,z,x1,x2,y1,y2;
26     while(scanf("%d%d",&op,&n)!=EOF)
27     {
28         memset(c,0,sizeof(c));
29         while(scanf("%d",&op)&&op!=3)
30         {
31             if(op==1)
32             {
33                 scanf("%d%d%d",&x,&y,&z);
34                 add(x+1,y+1,z);
35             }
36             else
37             {
38                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
39                 x1++,x2++,y1++,y2++;
40                 printf("%d\n",q(x2,y2)+q(x1-1,y1-1)-q(x2,y1-1)-q(x1-1,y2));
41             }
42         }
43     }
44     return 0;
45 }
46 /*
47 i -= lowbit(i)   ==      i = i&(i-1)
48 i += lowbit(i)   ==      i = (i|(i-1))+1
49 */

參考文章：http://blog.csdn.net/hit_lingo/article/details/50845718

　　　　 ??http://www.cnblogs.com/yejinru/archive/2012/03/22/2412359.html

轉載于:https://www.cnblogs.com/L-King/p/5445612.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/255432.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/255432.shtml
英文地址，請注明出處：http://en.pswp.cn/news/255432.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！