优美的二维树状数组

有一类求一段区间内所有数字的和的问题,以前我是用前缀和数组解决的。
今天遇到了二维的树状数组,发现它的代码非常优美,就把这两者一起写一写吧。

1. 一维前缀和数组

假设共有n个数字,我们把它们存放在a数组中

1
2
for (int i=1;i<=n;i++)
std::cin>>a[i];

然后,我们用sum[i]表示a[1]+a[2]+…+a[i],
显然sum[i]=sum[i-1]+a[i];
很容易就求出了前缀和数组

1
2
3
sum[0]=0;
for (int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i]

当我们要计算l到r闭区间内的所有数字的和时,可以用sum[r]-sum[l-1]求出

1
2
3
int getSum(int l,int r){
return sum[r]-sum[l-1];
}

2. 二维前缀和数组

如果我们的数字一共有n行m列,想求从左上角(x1,y1)到右下角(x2,y2)的矩形内的数字的和,也可以使用前缀和。
我们把数字存放在a[i][j]中,从(1,1)到(i,j)的矩形内数字的和存放在sum[i][j]中

1
2
3
4
5
6
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
std::cin>>a[i][j];
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}

为什么这样写?自己在草稿本上画一下图就明白了。
求和也非常简单

1
2
3
int getSum(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

前缀和数组预处理的时间复杂度是O(nm),查询的时间复杂度是O(1),非常快。
但是它有一个缺点就是修改很慢,每次修改一个点就要修改这个点后面的sum数组,时间复杂度是O(n
m)

3. 一维树状数组

树状数组查询和修改的时间都是O(log(n)),当有大量的修改时,我们应该使用树状数组
注意,这里的sum与前缀和中的sum不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lowbit(int x){
return -x&x;
}

void add(int x,int v){
//修改操作,给a[x]加上v
for (int i=x;i<=n;i+=lowbit(i))
sum[i]+=v;
}

int getSum(int x){
//查询a[1]+a[2]+...+a[x]的和
int ans = 0;
for (int i=x;i;i-=lowbit(i))
ans+=sum[i];
return ans;
}

int getSum(int l,int r){
//查询a[l]+a[l+1]+...+a[r]的和
return getSum(r)-getSum(l-1);
}

可以看到,两者的getSum非常像

3. 二维树状数组

二维树状数组简直就是一维树状数组和二维前缀和数组结合起来,查询的代码一模一样

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
const int maxn = 305;

struct STree {

int a[maxn][maxn];

int lowbit(int x){
return (-x)&x;
}

void add(int x,int y,int v){
for (int i=x;i<maxn;i+=lowbit(i)){
for (int j=y;j<maxn;j+=lowbit(j)){
a[i][j]+=v;
}
}
}

int query(int x,int y){
int ans = 0;
for (int i=x;i;i-=lowbit(i)){
for (int j=y;j;j-=lowbit(j)){
ans += a[i][j];
}
}
return ans;
}

int query(int x1,int y1,int x2,int y2){
return query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1);
}

};


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!