poj 1195 Mobile phones（二维树状数组）

题意：给你一个矩阵（初始化为0）和一些操作，1 x y a表示在arr[x][y]加上a，2 l b r t 表示求左上角为(l,b),右下角为(r,t)的矩阵的和。

分析：裸的二维树状数组。

代码如下：

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

View Code