二维树状数组模板题 POJ1195

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 int s[1500][1500],n,m;
 8 int lb(int i)
 9 {
10     return i&-i;
11 }
12 
13 void set(int i,int j,int x)
14 {
15     for(int ii=i;ii<=n;ii+=lb(ii))
16     {
17         for(int jj=j;jj<=m;jj+=lb(jj))
18         {
19             s[ii][jj]+=x;
20         }
21     }
22 }
23 
24 int get(int i,int j)
25 {
26     int ans=0;
27     for(int ii=i;ii>0;ii-=lb(ii))
28     {
29         for(int jj=j;jj>0;jj-=lb(jj))
30         {
31             ans+=s[ii][jj];
32         }
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     int o;
40     while(scanf("%d",&o))
41     {
42         if(o==0)
43         {
44             scanf("%d",&n);
45             m=n;
46             memset(s,0,sizeof(s));
47         }
48         else if(o==1)
49         {
50             int x,y,a;
51             scanf("%d%d%d",&x,&y,&a);
52             set(x+1,y+1,a);
53         }
54         else if(o==2)
55         {
56             int l,b,r,t;
57             scanf("%d%d%d%d",&l,&b,&r,&t);
58             cout<<get(r+1,t+1)-get(r+1,b)-get(l,t+1)+get(l,b)<<endl;
59         }
60         else if(o==3)
61             break;
62     }
63     return 0;
64 }
View Code
二维树状数组 模板题 POJ1195

二维树状数组模板题 POJ1195
