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

 1 /*
 2 题意 ：
 3   改变矩阵中元素值 ，求子矩阵的和
 4   二维树状数组，
 5 */
 6 
 7 #include<stdio.h>
 8 #define N 1050
 9 int s;
10 int map[N][N];
11 int lowbit(int x)
12 {
13     return x&(-x);
14 }
15 void add(int x,int y,int d)
16 {
17     int i=x;
18     int j=y;
19     while(i<=s)
20     {
21         j=y;
22         while(j<=s)
23         {
24             map[i][j]+=d;
25             j=j+lowbit(j);
26         }
27         i=i+lowbit(i);
28     }
29 }
30 int sum(int l,int b)
31 {
32     int i=l;
33     int j=b;
34     int ans=0;
35     while(i>0)
36     {
37         j=b;
38         while(j>0)
39         {
40             ans+=map[i][j];
41             j-=lowbit(j);
42         }
43         i-=lowbit(i);
44     }
45     return ans;
46 }
47 int main()
48 {
49     int l,i,j,x,y,d,L,b,r,t;
50     while(scanf("%d",&l)!=EOF)
51     {
52         if(l==3)break;
53         if(l==0)
54         {
55             scanf("%d",&s);
56             for(i=0;i<=s;i++)
57               for(j=0;j<=s;j++)
58                 map[i][j]=0;
59 
60         }
61         if(l==1)
62         {
63             scanf("%d%d%d",&x,&y,&d);
64             if(map[x+1][y+1]+d<0)continue;
65             add(x+1,y+1,d);
66         }
67         if(l==2)
68         {
69             scanf("%d%d%d%d",&L,&b,&r,&t);
70            int ans;
71              
72 
73            ans=sum(r+1,t+1)-sum(L,t+1)-sum(r+1,b)+sum(L,b);
74 
75             printf("%d\n",ans);
76         }
77     }
78 }
poj 1195 Mobile phones （二维 树状数组）

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