では、ゲームを始めましょう
GO FOR IT !

引言

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

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

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

首先

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

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

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

让我们思考:

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

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

简单思考,可以做出一个二叉树:

image-20211017212421036

再给它的小圆点标上标记,方便说明:

image-20211017212905834

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

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

image-20211017213145220

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

image-20211017213514652

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

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

​ 前缀和(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)

现在我们知道了:

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

继续优化:

image-20211017215537352

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

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

​ 这里给一个简易的动画:

动画

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

image-20211017221416768

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

image-20211017221833418

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

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

image-20211017222235098

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

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

是不是有种豁然开朗的感觉?(别说没有

总访问量 访问人数