TOC
介绍线段树前,先了解一下树状数组。他们两个功能差不多,不过有些线段树能够解决的问题,树状数组未必能解决。
树状数组(binary indexed tree)
首先思考一个场景,当有个需求让你求数组中某个区间(0-n、n-m)的和,通常做法是遍历数组求和的方式。这个复杂度为 O(N),但是当区间长度趋向于无穷大时,遍历的开销就不能够忽视了。可以通过树状数组来优化,将区间求和复杂度降低到 O(logN)。
先看一个简单树状结构:
1-8
/ \
1-4 5-8
/ \ / \
1-2 3-4 5-6 7-8
/ \ / \ / \ / \
1 2 3 4 5 6 7 8
我们可以使用如上的完全二叉树来优化,节点中存储子树的区间和,这样每次求和时可以使用数节点来优化。例如:Sum(3,7)=Sum(3-4)+Sum(5-6)+Sum(7)。但是这样结构带来几个问题:
- 存储空间增加一倍(2*n),每个树节点都需要一个空间记录子空间和;
- 代码实现复杂度高;
- 其中有些节点重复,例如 Sum(3-4) 可以根据 Sum(1-4) 和 Sum(1-2) 计算出来,不需要重复存储;
那么,我们可以将上面结构进行变形,减少存储空间:
1-8
/ |
1-4 5-8
/ | / |
1-2 3-4 5-6 7-8
/ | / | / | / |
1 2 3 4 5 6 7 8
变形后会发现,每一列的最顶端的节点是叶子节点的累加和,即:
Sum(1-8) = Sum(1) + Sum(2) + …. + Sum(8) Sum(7) = Sum(7) Sum(1-4) = Sum(1) + Sum(2) + Sum(3) + Sum(4) Sum(5-6) = Sum(5) + Sum(6)
所以只需要 O(N) 的存储空间就能够表示数组的个区间和:
Bit[8] = Sum(8)
Bit[7] = Sum(7)
Bit[6] = Sum(6)
... ...
那下面问题是,如何编码实现呢?有人给出了一个算法 lowbit = n&(-n),它主要求一个数字的二进制表示,右边第一位为1的数字,例如 6 二进制为 0110,lowbit(6) = 2。类似于 cidr 网段的划分 0110 包含的段为 0110 和 0111,其实就是 (0110 -lowbit(0110)+1, 0110)
的区间。
那么 Sum(n) 表达公式为: Sum(n) = Sum(n) + … + Sum(n-lowbit+1)。
那么就伪代码可以编写为:
func update(idx, diff):
for idx <= n:
Sum(idx) += diff
idx += lowbit(idx)
func getSum(idx):
for idx > 0:
sum += Sum(idx)
idx -= lowbit(idx)
「真诚赞赏,手留余香」
真诚赞赏,手留余香
使用微信扫描二维码完成支付

comments powered by Disqus