引言

因为高三备考，一年多没打过代码，现在要参加ACM，赶紧把算法复习一下。

复习到树状数组的时候，我就在想，我肯定是还没有理解到精髓，不然怎么会仅仅几行的板子都记不住。

所以我看了很多文章，又从树状数组如何被发明出来这个角度进行思考，总算有种顿悟的感受。

首先

我们先记住发明者Peter M. Fenwick——因为后面我们根本不会再接触他了

树状数组的诞生我们就不管了，因为初衷和现在最常用作的“前缀和”用法可能没有关系

我们以下的思路全部建立在解决前缀和问题

让我们思考：

如果说一个算法和什么玄学扯上关系的时候就可以有着log的优化，毫无疑问，我们本能的——“ 和二进制相关！”

那么，考虑一个8个数的数组，我们要维护它的前缀和。

简单思考，可以做出一个二叉树：

再给它的小圆点标上标记，方便说明：

如上图，比如我们要求前8位的前缀和，非常简单，我们直接存储在 [1,8] 这个元素里了

那如果是前7位的前缀和呢？

前7位的前缀和在这里面，不像前八位可以直接储存在**[1,8]**这个元素里，那么我们要将几个元素相加

简单思考可以知道，如上“粉色”标记的元素，相加后就可以得到前七位的前缀和

我们通过数字标记写出来就是：

前缀和（7）= [1,4] + [5,6] + [7]

这样还看不出什么，全部写出来看看：

前缀和（8）= [1,8]

前缀和（7）= [1,4] + [5,6] +[7]

前缀和（6）= [1,4] + [5,6]

前缀和（5）= [1,4] + [5]

前缀和（4）= [1,4]

前缀和（3）= [1,2] + [3]

前缀和（2）= [1,2]

前缀和（1）= [1]

写了这么多，从对齐的规律，已经可以看出一些感觉了。

如果还是没有头脑，那我们再看看每个子区间的长度有什么规律：

子区间长度（8）= 8

子区间长度（7）= 4 + 2 +1

子区间长度（6）= 4 + 2

子区间长度（5）= 4 + 1

子区间长度（4）= 4

子区间长度（3）= 2 + 1

子区间长度（2）= 2

子区间长度（1）= 1

现在答案已经不言而喻了，这不就是十进制数字变成二的幂次相加吗！

以（7）为例：子区间长度（7）= 4 + 2 + 1 = 22 + 21 + 20 ，对应十进制数字7的二进制就是（111）

现在我们知道了：

通过拆成二的幂次相加形式，我们可以迅速得到我们需要的“子区间长度”，那么求子区间现在就没有问题了

继续优化：

如图中所示，我们现在创建了8+7=15个节点用来储存数据，但是我们目标是前缀和

那么其实：正方形元素的 2, 4, 6, 8我们都不会用到！圆形元素的 [3,4], [7,8], [5,8]也用不上！不明白可以思考一下

这里给一个简易的动画：

所以，实际上，我们只需要15-7=8个元素，就可以储存下全部所需的数据

据此，我们重画一下这棵树，去掉不要的点：

是不是DNA动了？这和普通算法书上的图已经非常像了

我们再拉直线段，把[1,2]这样的元素重命名一下：

现在我们就得到了已经烂大街的树状数组结构图。

直接看这个图，难以理解，但是通过上面的推导，我想各位已经很清楚了。

是不是有种豁然开朗的感觉？（别说没有