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