POJ1195

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define N 1026
 5 int c[N][N],s;
 6 int lowbit(int i){
 7     return i&(-i);
 8 }
 9 void update(int x,int y,int val){
10     int i,j;
11     for(i=x;i<=s;i+=lowbit(i))
12         for(j=y;j<=s;j+=lowbit(j))
13             c[i][j]+=val;
14     return ;
15 }
16 int getsum(int x,int y){
17     int i,j,ss=0;
18     for(i=x;i>=1;i-=lowbit(i))
19         for(j=y;j>=1;j-=lowbit(j))
20             ss+=c[i][j];
21     return ss;
22 }
23 int main(){
24     int i,j,k,t,a,b,cc,x,y;
25     memset(c,0,sizeof(c));
26     while(scanf("%d",&k)&&k!=3){
27         if(k==0){
28             scanf("%d",&s);
29         }else
30             if(k==1){
31                 scanf("%d%d%d",&a,&b,&cc);
32                 a++;
33                 b++;
34                 update(a,b,cc);
35             }
36             else{
37                 scanf("%d%d%d%d",&x,&y,&a,&b);
38                 a++;
39                 b++;
40                 x++;
41                 y++;
42                 printf("%d\n",getsum(a,b)+getsum(x-1,y-1)-getsum(a,y-1)-getsum(x-1,b));
43             }
44     }
45     return 0;
46 }

二维树状数组

更新一个点(x,y );所以只要更新与它有关的几个点。向上更新到s；

求和就是同样的，向下求和。

每次输入坐标都要++，防止求和时候 i 出现==0的情况。

keep moving...