树状数组的缘起

相信大家对数组这一基础的数据结构都有所了解， 本质上数组在内存中是一段连续的地址, 我们可以通过地址偏移来访问元素，这个操作在计算机中效率是非常高的, 时间复杂度为O(1), 但是如果我们要对一个数组求和的话， 时间复杂度为O(n)。

想要优化数组求和的复杂度的话，你可能会想到会求前缀和数组来实现O(1)的效果, 但是如果要修改数组里面的值, 就要修改前缀和里面的值, 时间复杂度为O(n)。

于是就有了两种极端, 那么有没有一种既能快速查询也能快速求和的数据结构呢?

什么是树状数组(Fenwick Tree)？

说白了本质上就是用数组去模拟一颗树,  更新和求和的复杂度都为O(logn) (这个后面会证明)

要理解用数组是怎么去构建一颗树, 实际上很简单, 我们先了解一下关于二进制的性质

我们知道对于任何正整数x, 都可以将它分解为二进制位权展开的形式:

树状数组本质上就是通过二进制的位权展开来对求和进行优化的, 如果我们能把一个数组分为不同的区间, 并从小区间开始求和, 在利用保存过的小区间的值去推算出大区间的值。从此优化了求和的效率. 例如我们要对一个长度n = 256的数组求和, 如果用一个for循环我们要算256次, 但利用树状数组只需要计算8次。

下面给出几个例子, tree代表树状数组, a代表原数组:

• tree[1] = A[1];

• tree[2] = A[1] + A[2];

• tree[3] = A[3];

• tree[4] = tree[2] + A[3] + A[4]

             = A[1] + A[2] + A[3] + A[4];

• tree[5] = A[5];

• tree[6] = A[5] + A[6];

• tree[7] = A[7];

• tree[8] =  tree[4] + tree[6] + A[7] + A[8] 

            =A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

于是我们可以发现树状数组的几个性质:

tree[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i]

其中 k 是二进制中最后一个1的值。

如何理解呢? 通过继续观察我们可以发现当 i 为奇数时, tree[i] = A[i] 总是成立的, 比如上面的 tree[3] = A[3], tree[5] = A[5], tree[7] = A[7]。

如何证明这一性质呢? 下面我们来证明: 当 n 是奇数时, 当且仅当 n 的二进制最后一位为 1 .

假设 n = 2 * m + 1, 因为 n % 2 = 1，所以当我们在将 n 转换为二进制的过程中 (不断 / 2 取余数) 最后一位必定为 1， 证毕。

对称地,  当 n 为偶数时, 最后一位不为 0。 这就是为什么 n 为偶数时 tree[n] 都可以分解为 至少两个区间的和了。 例如 2 (10), 4 (100), 6 (110)...

那么我们就理解了 k 的含义: 二进制中最后一个1的值。

如何实现树状数组

分析了树状数组的性质后, 我们就可以更任意地实现树状数组了。

首先我们定义函数 k = lowbit(i) 来求出 i 的进制中最后一个1的值并赋值给 k

我们可以证明以下性质: 当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子

这里利用了负数的补码存储，当x为0时, 结果很显然是0, 当x为奇数时, 因为补码 = 反码 + 1,

那么 -x 的最后一位必然是 1, 于是x 和 -x 除了最后一位都为 1 外其他为都相反, 于是我们按位与后的结果为 1

当 x 为偶数的时候, 我们可以通过讨论 x 是否为 2 次幂来证明这个函数的正确性, 思路大致都一样，这里就不详细写了。。。

于是我们可以构建出我们的求和函数了， 只要 i 不为0，我们就一直让它减去 lowbit(i), 相当于上述的整数分解为二进制的过程:

如何实现更新树状数组里面的元素呢? 我们考虑从子节点向父节点更新(向上更新)我们也可以快速地写出代码了:

证明树状数组的时间复杂度

最后再模仿<<算法导论>>里的套路, 证明一下时间复杂度吧! 

已知我们把数组分解成了最多logx个区间, 那么我们只需对每个区间求和就可以得到整个数组的和, 如果有n个元素, 那么很容易推出求和的时间复杂度为O(logn)。

下面我们来证明更新时的复杂度为 O(logn), 由于查询是从子节点向上更新的, 那么要爬到 n 也需要 log (n - i) 次, 那么时间复杂度也是 O(logn)级别的。

总结

本蒟蒻学这个算法时也很蒙蔽，主要当时二进制的思想还理解得不够深,  实际上这个算法的优雅之处在于用二进制的将一个数组拆分来进行优化, 而且代码比起线段树也很简洁, 据说还有大佬能用树状数组实现一颗平衡树。 这种用倍增的思想去降低时间复杂度的技巧还是值得我们去学习的。 

最后在把代码献上吧: