数状数组
树状数组
树状数组或二元索引树（Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。
其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以O(log n)的时间得到任意前缀和，并同时支持在O(log n)时间内支持动态单点值的修改。空间复杂度O(n)
怎么理解树状数组要解决的问题呢？
举例来说，树状数组所能解决的典型问题就是存在一个长度为n的数组，我们如何高效进行如下操作：
- add(idx, num)：将num加到位置idx的数字上。
- prefixSum(idx)：求从数组第一个位置到第idx（含idx）的所有数字的和。
- rangeSum(from_idx, to_idx)：求从数组第from_idx个位置到第to_idx个位置的所有数字的和
要解决以上问题，可以有以下几种思路
- 最开始想到的，肯定就是直接基于原数组去暴力实现这几个函数，这样，add就是O(1)时间复杂度，predixSum就是O(n)时间复杂度，rangeSum(from_idx，to_idx)也是O(n)时间复杂度，但是一般这种是不符合要求的，本来就是要解决特定场景下的问题，查询的时间复杂度太高
- 或者再建立一个前缀和数组，每一位保存前面所有数的累加值，额外的空间复杂度是O（n），prefixSum(idx)时间复杂度是O(1)，rangeSum(from_idx，to_idx)=prefixSum(to_idx)-prefixSum(from_idx)时间复杂度为O(1)，但是add(idx，num)就需要更新idx到数组末尾的每一个位的值，时间复杂度O（n），除非add操作非常低频，否则这种做法也不合适
数组数组这种数据结构能平衡求前缀和和更新操作，使之都是O（logn）时间复杂度，虽然需要额外的O（n）空间
怎么做到的
数状数组逻辑上可以看作一颗多叉树，父节点等于子节点之和，但是实际存储还是按照数组的形式来存储数组的。 树状数组的父节点和子节点的下标关系是parent = son + 2^k，其中 k 是子节点下标对应二进制末尾 0 的个数，也就是说一个节点的子节点是符合以下条件的节点：子节点的下标加上下标二进制形式最末尾的1所代表的数等于父节点的下标。
比如8的二进制是 0b1000，那么有 7（0b111）加上最末尾的1正好等于8、6（0b110）加上最末尾的1也就是2（0b10）正好等于8、4（0b100）加上最末尾的1也就是4（0b100）正好等于8……
再观察上图，可以发现一些规律
- 树状数组里奇数节点正好等于原数组对应节点的值，因为奇数在最末尾肯定是1，1后面没有0。有2个子节点的，正好其二进制末尾的1后面有1个0。有3个子节点的，正好末尾后面有2个0。有4个子节点的，其末尾后面有3个0。可以引申一个节点的子节点的个数 n = k + 1，其中 k 是子节点下标对应二进制末尾 0 的个数
- 树状数组里某个节点的值对应原数组m个节点的值累加，m=2^k，其中 k 是子节点下标对应二进制末尾 0 的个数。且这m个节点是连续的
- 树状节点的下标为i，那对应到原数组里m个连续节点的左边界是i-2^k+1，右边界是i。其中 k 是子节点下标对应二进制末尾 0 的个数
可以发现树状节点很重要的一个操作是要求序号二进制最后一位1，也就是lowbit，可以定义一个函数：
func lowBit(x int) int {
return x & -x
}
这里用到了位运算的技巧，因为数值在计算机中都是用补码表示的，负数等于正数原码按位取反再+1，再和原数进行 & 操作就可以得到lowbit，随便找个数换成二进制形式算一下就能理解了。
那数状数组怎么求前缀和呢？上面规律的第三点很关键，可以理解成，树状节点的值代表对应原数组节点序号减去其lowbit的下一个数到此序号的累加。去掉lowbit就可以得到紧挨着的前一个范围内的范围和，一直递归到最开始，就可以累加得到前缀和，举个例子：
求原数组0-14的前缀和：
- 树状数组序号为14（0b1110）的节点包括原数组从13（0b1101）到14（0b1110）的累加。
- 去掉lowbit得到12（0b1100），树状数组序号为12的节点包括9（0b1001）到12（ob1100）的累加
- 再去掉一个lowbit，得到8（0b1000），树状数组序号为8的节点包括1到8（0b1000）的累加。加起来刚好0-14的前缀和。
数学证明引用大佬的一张图（看参考链接）：
所以可以发现这其实是个递归的操作，那么可以实现PrefixSum查询：
// 时间复杂度O(logn)
func PrefixSum(tree []int, idx int) int {
sum := 0
for idx >= 1 {
sum += tree[idx]
idx -= lowBit(idx)
}
return sum
}
从原数组建树有两种方式，一种O（nlogn）复杂度，一种O（n）复杂度
- 第一种，其实就是利用上面说的规律三，也就是直接根据每个树状数组下标和原数组下标的关系构建起来的，注意，如上图，树状数组实际下标应该从1开始，所以在构建的时候下标要+1。
- 第二种，是递增式分多次构建一个节点的值，每个节点在完成自己节点构建后，会把自己节点的值也加到父节点上，补齐父节点的值的一部分，这样按照正序遍历，只需要一次遍历就可以完成所有节点的构建，很巧妙
// O(nlogn)时间复杂度建树
func BuildBinaryIndexedTree(raw []int) []int {
tree := make([]int, len(raw)+1)
for i := 1; i <= len(raw); i++ {
for j := i - lowBit(i); j <= i-1; j++ {
tree[i] += raw[j]
}
}
return tree
}
func getParent(idx int) int {
low := lowBit(idx)
return idx + low
}
// O(n)时间复杂度建树
func BuildBinaryIndexedTree2(raw []int) []int {
tree := make([]int, len(raw)+1)
for i := 1; i <= len(raw); i++ {
tree[i] += raw[i-1]
parent := getParent(i)
if parent <= len(raw) {
tree[parent] += tree[i]
}
}
return tree
}
因为树状数组父节点和子节点的下标关系是parent = son + 2^k，所以更新一个节点的时候，要递归更新所有其祖先节点的值：
// O（logn）时间复杂度
func Add(tree []int, idx int, val int) {
for idx <= len(tree) {
tree[idx] += val
idx += lowBit(idx)
}
}
上面已经实现了获取节点父节点操作，接下来实现获取所有子节点下标的操作
// O(logn)时间复杂度
func getChildren(idx int) []int {
low := lowBit(idx)
children := []int{idx}
base := idx - low
for low > 1 {
low >>= 1
base += low
children = append(children, base)
}
return children
}
如果不是求前缀和，而是求一个范围的累加和RangeSum，比如[i,j]，因为PrefixSum求的是[1, i]的累加值，所以RangeSum(i,j) = PrefixSum(j) - PrefixSum(i-1)
// O(logn)时间复杂度
func rangeSum(tree []int, start, end int) int {
return PrefixSum(tree, end) - PrefixSum(tree, start-1)
}
参考链接
https://zh.m.wikipedia.org/zh-hans/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
https://halfrost.com/binary_indexed_tree/#toc-0
https://oi-wiki.org/ds/fenwick/