# 数据结构：二维树状数组、三维树状数组

2018/07/19 16:21

void update(int x,int y,int z)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
c[i][j]+=z;
}

int sum(int x,int y)
{
int ret=0;
for(int i=x;i>=1;i-=lowbit(i))
for(int j=y;j>=1;j-=lowbit(j))
ret+=c[i][j];
return ret;
}

int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<endl;

 1 #include<iostream>
2 using namespace std;
3 const int maxn=1005;
4 const int maxm=1005;
5 int n,m;
6 int q;
7 int a[maxn][maxm];
8 int c[maxn][maxm];
9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void update(int x,int y,int z)
14 {
15     for(int i=x;i<=n;i+=lowbit(i))
16     for(int j=y;j<=m;j+=lowbit(j))
17         c[i][j]+=z;
18 }
19
20 int sum(int x,int y)
21 {
22     int ret=0;
23     for(int i=x;i>=1;i-=lowbit(i))
24     for(int j=y;j>=1;j-=lowbit(j))
25         ret+=c[i][j];
26     return ret;
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1;i<=n;i++)
32     for(int j=1;j<=m;j++)
33     {
34         cin>>a[i][j];
35         update(i,j,a[i][j]);
36     }
37     cin>>q;
38     while(q--)
39     {
40         int x;
41         cin>>x;
42         if(x==1)
43         {
44             int y,z,w;
45             cin>>y>>z>>w;
46             update(y,z,w);
47         }
48         if(x==2)
49         {
50             int x1,y1,x2,y2;
51             cin>>x1>>y1>>x2>>y2;
52             cout<<sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<endl;
53         }
54     }
55     return 0;
56 }

            update(x1,y1,w);
update(x2+1,y2+1,w);
update(x2+1,y1,-w);
update(x1,y2+1,-w);

 1 #include<iostream>
2 using namespace std;
3 const int maxn=1005;
4 const int maxm=1005;
5 int n,m;
6 int q;
7 int a[maxn][maxm];
8 int c[maxn][maxm];
9 int lowbit(int x)
10 {
11     return x&(-x);
12 }
13 void update(int x,int y,int z)
14 {
15     for(int i=x;i<=n;i+=lowbit(i))
16     for(int j=y;j<=m;j+=lowbit(j))
17         c[i][j]+=z;
18 }
19
20 int sum(int x,int y)
21 {
22     int ret=0;
23     for(int i=x;i>=1;i-=lowbit(i))
24     for(int j=y;j>=1;j-=lowbit(j))
25         ret+=c[i][j];
26     return ret;
27 }
28 int main()
29 {
30     cin>>n>>m;
31     cin>>q;
32     while(q--)
33     {
34         int x;
35         cin>>x;
36         if(x==1)
37         {
38             int x1,y1,x2,y2,w;
39             cin>>x1>>y1>>x2>>y2>>w;
40             update(x1,y1,w);
41             update(x2+1,y2+1,w);
42             update(x2+1,y1,-w);
43             update(x1,y2+1,-w);
44         }
45         if(x==2)
46         {
47             int x,y;
48             cin>>x>>y;
49             cout<<sum(x,y)<<endl;
50         }
51     }
52     return 0;
53 }

int x1,y1,x2,y2,w;
cin>>x1>>y1>>x2>>y2>>w;
update(c1,x1,y1,w),update(c1,x1,y2+1,-w);
update(c1,x2+1,y1,-w),update(c1,x2+1,y2+1,w);

update(c2,x1,y1,w*x1),update(c2,x2+1,y1,-w*(x2+1));
update(c2,x1,y2+1,-w*x1),update(c2,x2+1,y2+1,w*(x2+1));

update(c3,x1,y1,w*y1),update(c3,x2+1,y1,-w*y1);
update(c3,x1,y2+1,-w*(y2+1)),update(c3,x2+1,y2+1,w*(y2+1));

update(c4,x1,y1,w*x1*y1),update(c4,x2+1,y1,-w*(x2+1)*y1);
update(c4,x1,y2+1,-w*x1*(y2+1)),update(c4,x2+1,y2+1,w*(x2+1)*(y2+1));

int get(int x,int y)
{
return sum(c1,x,y)*(x+1)*(y+1)-sum(c2,x,y)*(y+1)-(x+1)*sum(c3,x,y)+sum(c4,x,y);
}

int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1)<<endl;

 1 #include<iostream>
2 using namespace std;
3 const int maxn=1005;
4 const int maxm=1005;
5 int n,m;
6 int q;
7 int a[maxn][maxm];
8 int c1[maxn][maxm];
9 int c2[maxn][maxm];
10 int c3[maxn][maxm];
11 int c4[maxn][maxm];
12 int lowbit(int x)
13 {
14     return x&(-x);
15 }
16 void update(int c[][maxm],int x,int y,int z)
17 {
18     for(int i=x;i<=n;i+=lowbit(i))
19     for(int j=y;j<=m;j+=lowbit(j))
20         c[i][j]+=z;
21 }
22
23 int sum(int c[][maxm],int x,int y)
24 {
25     int ret=0;
26     for(int i=x;i>=1;i-=lowbit(i))
27     for(int j=y;j>=1;j-=lowbit(j))
28         ret+=c[i][j];
29     return ret;
30 }
31
32 int get(int x,int y)
33 {
34     return sum(c1,x,y)*(x+1)*(y+1)-sum(c2,x,y)*(y+1)-(x+1)*sum(c3,x,y)+sum(c4,x,y);
35 }
36 int main()
37 {
38     cin>>n>>m;
39     cin>>q;
40     while(q--)
41     {
42         int x;
43         cin>>x;
44         if(x==1)
45         {
46             int x1,y1,x2,y2,w;
47             cin>>x1>>y1>>x2>>y2>>w;
48             update(c1,x1,y1,w),update(c1,x1,y2+1,-w);
49             update(c1,x2+1,y1,-w),update(c1,x2+1,y2+1,w);
50
51             update(c2,x1,y1,w*x1),update(c2,x2+1,y1,-w*(x2+1));
52             update(c2,x1,y2+1,-w*x1),update(c2,x2+1,y2+1,w*(x2+1));
53
54             update(c3,x1,y1,w*y1),update(c3,x2+1,y1,-w*y1);
55             update(c3,x1,y2+1,-w*(y2+1)),update(c3,x2+1,y2+1,w*(y2+1));
56
57             update(c4,x1,y1,w*x1*y1),update(c4,x2+1,y1,-w*(x2+1)*y1);
58             update(c4,x1,y2+1,-w*x1*(y2+1)),update(c4,x2+1,y2+1,w*(x2+1)*(y2+1));
59         }
60         if(x==2)
61         {
62             int x1,y1,x2,y2;
63             cin>>x1>>y1>>x2>>y2;
64             cout<<get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1)<<endl;
65         }
66     }
67     return 0;
68 }

（如果有人出三维树状数组修改区间查询区间的那种题，直接在二维树状数组修改区间查询区间的基础上改，应该不会有这种题的）

 1 #include<iostream>
2 using namespace std;
3 const int maxn=105;
4 const int maxm=105;
5 const int maxl=105;
6 int n,m,l;
7 int q;
8 int a[maxn][maxm][maxl];
9 int c[maxn][maxm][maxl];
10 int lowbit(int x)
11 {
12     return x&(-x);
13 }
14 void update(int x,int y,int z,int w)
15 {
16     for(int i=x;i<=n;i+=lowbit(i))
17     for(int j=y;j<=m;j+=lowbit(j))
18     for(int k=z;k<=l;k+=lowbit(k))
19         c[i][j][k]+=w;
20 }
21
22 int sum(int x,int y,int z)
23 {
24     int ret=0;
25     for(int i=x;i>=1;i-=lowbit(i))
26     for(int j=y;j>=1;j-=lowbit(j))
27     for(int k=z;k>=1;k-=lowbit(k))
28         ret+=c[i][j][k];
29     return ret;
30 }
31 int main()
32 {
33     cin>>n>>m>>l;
34     cin>>q;
35     while(q--)
36     {
37         int x;
38         cin>>x;
39         if(x==1)
40         {
41             int x1,y1,z1,x2,y2,z2,w;
42             cin>>x1>>y1>>z1>>x2>>y2>>z2>>w;
43              update(x1,y1,z1,w);
44              update(x1,y2+1,z1,-w);
45              update(x2+1,y1,z1,-w);
46              update(x2+1,y2+1,z1,w);
47
48              update(x1,y1,z2+1,-w);
49              update(x1,y2+1,z2+1,w);
50              update(x2+1,y1,z2+1,w);
51              update(x2+1,y2+1,z2+1,-w);
52         }
53         if(x==2)
54         {
55             int x,y,z;
56             cin>>x>>y>>z;
57             cout<<sum(x,y,z)<<endl;
58         }
59     }
60     return 0;
61 }

0
0 收藏

0 评论
0 收藏
0