论树状数组的正确食用方式
2024-09-15 17:24:49
发布于:上海
消灭线段树大常数暴政,世界属于树状数组。
挑战赛考虑出数据结构题吗?(
Part 0 基础知识
- 一点点的数学知识。
- 位运算知识: 表示 的二进制表示下最低位的一(与其后面的所有零构成的数)。
lowbit(x) = x & (-x)
。
等价于 。
Part 1 基本用法
Part 1.0 介绍
树状数组是一种支持单点修改和区间查询的高效数据结构。事实上,也可以通过一些进阶用法实现区间修改和单点查询,或者区间修改和区间查询,且渐进时空复杂度不会改变。
令当前树状数组的大小为 ,则单次修改或查询时间复杂度均为 。空间复杂度则恒为 。
一般的树状数组要求维护的信息满足结合律且存在逆运算。例如加法,模意义下的乘法(需保证逆元存在)等就满足上述条件,而类似于 , 等不存在逆运算,就无法直接维护。(事实上这一类存在结合律而不存在逆运算的也可以用树状数组维护,但是时间复杂度会退化为 ,劣于线段树的 ,所以不作讨论。)
发现树状数组使用的条件(结合律,逆运算)是使用线段树(结合律)的充分不必要条件,而二者的时空复杂度严格相等,看起来线段树还更全能一些,树状数组显得优势不大。但是树状数组的优势在于:
- 时间常数小。树状数组只需要用
while
循环迭代,而线段树需要进行复杂的递归过程。zkw 线段树消去了递归过程,但常数仍然较大。 - 空间常数小。树状数组只需要一倍空间,而线段树需要至少二倍空间,极端情况可能会达到树状数组的数倍。
- 编程复杂度低。树状数组只需要几次简单的迭代,代码长度只有十几行甚至更少;而线段树一般都需要数十上百行。
所以学习树状数组还是很有用的。
Part 1.1 引入
一个简单的问题:假如我想知道 的和,怎么算?
显然可以直接累加,需要将 个数都加一遍。
那么假如我知道了 ,, 这三段分别的和,还可以怎么求?
显然直接把这三段的和加起来即可,只需要计算 个数的和。
这便是树状数组的核心思想:将求 的结果拆分成不超过 个子问题,使得这些子问题的答案是已知的。 这也是运算需要满足结合律的原因。
令 为树状数组以下标 结尾掌管的一个区间(区间大小在下面给出)的和。例如我们有 个元素,树状数组 的结构是长这样的:
Part 1.2 区间查询
观察上图。发现 是 的和, 是 的和, 是 的和。因此 的和就是 。那么这个式子是我们肉眼发现的,有没有一般性的方法得到要把哪几个元素加起来呢?
首先,先考虑每一个索引掌管区间的长度如何确定。观察下表:
区间长度 | ||
---|---|---|
1 | 1 | (0001) |
2 | 2 | (0010) |
3 | 1 | (0011) |
4 | 4 | (0100) |
5 | 1 | (0101) |
6 | 2 | (0110) |
7 | 1 | (0111) |
8 | 8 | (1000) |
9 | 1 | (1001) |
10 | 2 | (1010) |
11 | 1 | (1011) |
发现 掌管的区间长度为 (定义在 Part 0 给出)。因此得到结论: 就是为 的和。
知道了区间长度,接下来考虑查询。例如查找 的和:
- 包含了 区间。加入答案,跳到左端点的前一个 ,也就是 。
- 包含了 区间。加入答案,跳到左端点的前一个 ,也就是 。
- 包含了 区间。加入答案,跳到左端点的前一个 ,也就是 。
- 不存在,结束过程。
图:
有了上述思路,很容易用迭代实现查询 的和:
int query(int k){
int sum=0;
while(k){
sum+=c[k];
k&=k-1; // 等价于 k-=lowbit(k);
}
return sum;
}
求 的和,使用前缀和的思想,结果显然为 query(y)-query(x-1)
。
时间复杂度正确性:每一次对 的修改都会去除 二进制下的一个 1
。 的位数为 ,因此时间复杂度为 。
Part 1.3 单点修改
设要更改 的值。为了保证效率,我们只需要更改 及其所有直接或间接祖先。由于 包含于 (证明见后文),所以我们可以这样做:每一次修改后将索引自增其 ,直到索引超过范围。一个实现:
void add(int k,int x){
while(k<=n){
c[k]+=x;
k+=lowbit(k);
}
}
下说明 包含 。
令 ,,。
则 ,同时 管辖的左边界为 。容易得知 。取最小值,此时 管辖的左边界为 ,简单推一下后可得 管辖的左边界小于等于 管辖的左边界。
因为 管辖的左边界 管辖的左边界 ,所以 (即 )包含 。证毕。
Part 1.4 初始化
一个显然的方式是 次单点修改,时间复杂度 。
当然还能做得更好。因为父亲的下标总是严格大于自己的下标,而父亲的值就是其所有直接儿子的子树加上自己得到的。所以我们从左往右遍历,逐个修改自己和直接父亲,将其加上自己的子树和就行了,有点类似于线段树建树的思想。时间复杂度 。注意判断越界。
void build(){
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
c[i]+=x;
if(i+lowbit(i)<=n)
c[i+lowbit(i)]+=c[i];
}
}
例题:【模板】树状数组 1
Part 2 维护一个差分数组
可以通过维护一个差分数组实现区间修改,单点查询。
咕咕咕
例题:【模板】树状数组 2
Part 3 维护两个树状数组
可以通过维护两个树状数组实现区间修改,区间查询。
例题:【模板】线段树 1
咕咕咕
全部评论 7
顶
3天前 来自 上海
1支持挑战赛出数据结构题(
3天前 来自 广东
1顶
3天前 来自 广东
1顶再说
3天前 来自 上海
1目前没有这个打算哦,之前出过,爆死
22小时前 来自 浙江
0@AC君
昨天 来自 广东
0顶
昨天 来自 上海
0
有帮助,赞一个