Peter_Matthew的博客

二维树状数组

2019-01-26

1
2
3
4
int lowbit(int x)
{
return x&(-x);
}

二维树状数组1

单点修改,矩阵查询。

1
2
3
4
5
6
7
8
void add(int x,int y,long long d)
{
int sy=y;
for(;x<=nx;x+=lowbit(x))
for(y=sy;y<=ny;y+=lowbit(y))
tree[x][y]+=d;
}
add(x,y,k);

1
2
3
4
5
6
7
8
9
long long ask(int x,int y)
{
long long s;
int sy=y;
for(s=0;x;x-=lowbit(x))
for(y=sy;y;y-=lowbit(y))
s+=tree[x][y];
return s;
}
1
2
3
4
5
6
7
8
9
10
long long range_ask(int xa,int ya,int xb,int yb)
{
long long s=0;
s+=ask(xb,yb);
s-=ask(xb,ya-1);
s-=ask(xa-1,yb);
s+=ask(xa-1,ya-1);
return s;
}
printf("%lld\n",range_ask(xa,ya,xb,yb));

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
long long tree[1005][1005];
int nx,ny;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,long long d)
{
int sy=y;
for(;x<=nx;x+=lowbit(x))
for(y=sy;y<=ny;y+=lowbit(y))
tree[x][y]+=d;
}
void range_add(int xa,int ya,int xb,int yb,long long d)
{
add(xa,ya,d);
add(xa,yb+1,-d);
add(xb+1,ya,-d);
add(xb+1,yb+1,d);
}
long long ask(int x,int y)
{
long long s;
int sy=y;
for(s=0;x;x-=lowbit(x))
for(y=sy;y;y-=lowbit(y))
s+=tree[x][y];
return s;
}
long long range_ask(int xa,int ya,int xb,int yb)
{
long long s=0;
s+=ask(xb,yb);
s-=ask(xb,ya-1);
s-=ask(xa-1,yb);
s+=ask(xa-1,ya-1);
return s;
}
int q;
int main()
{
scanf("%d%d%d",&nx,&ny,&q);
for(int i=1,opt,x,y,xa,xb,ya,yb;i<=q;i++)
{
scanf("%d",&opt);
if(opt==1)
{
long long k;
scanf("%d%d%lld",&x,&y,&k);
add(x,y,k);
}
if(opt==2)
{
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
printf("%lld\n",range_ask(xa,ya,xb,yb));
}
}
}

二维树状数组2

矩阵修改,单点查询。

1
2
3
4
5
6
7
void add(int x,int y,long long d)
{
int sy=y;
for(;x<=nx;x+=lowbit(x))
for(y=sy;y<=ny;y+=lowbit(y))
tree[x][y]+=d;
}

1
2
3
4
5
6
7
8
void range_add(int xa,int ya,int xb,int yb,long long d)
{
add(xa,ya,d);
add(xa,yb+1,-d);
add(xb+1,ya,-d);
add(xb+1,yb+1,d);
}
range_add(xa,ya,xb,yb,k);
1
2
3
4
5
6
7
8
9
10
long long ask(int x,int y)
{
long long s;
int sy=y;
for(s=0;x;x-=lowbit(x))
for(y=sy;y;y-=lowbit(y))
s+=tree[x][y];
return s;
}
printf("%lld\n",ask(x,y));

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
long long tree[1005][1005];
int nx,ny;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,long long d)
{
int sy=y;
for(;x<=nx;x+=lowbit(x))
for(y=sy;y<=ny;y+=lowbit(y))
tree[x][y]+=d;
}
void range_add(int xa,int ya,int xb,int yb,long long d)
{
add(xa,ya,d);
add(xa,yb+1,-d);
add(xb+1,ya,-d);
add(xb+1,yb+1,d);
}
long long ask(int x,int y)
{
long long s;
int sy=y;
for(s=0;x;x-=lowbit(x))
for(y=sy;y;y-=lowbit(y))
s+=tree[x][y];
return s;
}
long long range_ask(int xa,int ya,int xb,int yb)
{
long long s=0;
s+=ask(xb,yb);
s-=ask(xb,ya-1);
s-=ask(xa-1,yb);
s+=ask(xa-1,ya-1);
return s;
}
int q;
int main()
{
scanf("%d%d%d",&nx,&ny,&q);
for(int i=1,opt,x,y,xa,xb,ya,yb;i<=q;i++)
{
scanf("%d",&opt);
if(opt==1)
{
long long k;
scanf("%d%d%d%d%lld",&xa,&ya,&xb,&yb,&k);
range_add(xa,ya,xb,yb,k);
}
if(opt==2)
{
scanf("%d%d",&x,&y);
printf("%lld\n",ask(x,y));
}
}
}

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章