「树状数组」第 2 节:理解预处理数组 C
「树状数组」第 2 节:理解预处理数组 C
我们看看树状数组长什么样。
树状数组的样子
例 5
我们以一个有 8 个元素的数组 A
为例(如上图),在数组 A
之上建立一个数组 C
,使得数组 C
的形成如上的一个多叉树形状,数组 C
就形成了一个树状数组的结构。以下是两点说明:
-
树状数组要建成动态的树形结构吗?
- 不用。学习过堆、线段树的朋友一定知道,使用数组就能方便地索引左右孩子结点、双亲结点(因为规律特别容易找到),这样的树就不必创建成结点、指针那样的动态树形结构。
-
如何解释「前缀和」查询和「单点更新」操作?
- 如果要查询「前缀和(4)」,本来应该查
A1
、A2
、A3
、A4
,然后把它们相加; - 有了数组
C
之后,我们只要问C4
即可; - 我们要更新结点
A1
的值,只要自底向上更新C1
、C2
、C4
、C8
的值即可。
- 如果要查询「前缀和(4)」,本来应该查
我们构建好数组 C
以后,就完全可以抛弃数组 A
了。
理解数组 C 的定义
-
首先我们强调一点,树状数组的下标从 开始,下标 号我们不用,这一点我们看到后面就会明白。我们先了解如下的定义,请大家一定先记住这些记号所代表的含义:
- 数组
C
是一个对原始数组A
的预处理数组。
- 数组
-
我们还要熟悉几个记号。为了方便说明,避免后面行文啰嗦,我们将固定使用记号 、 、 ,它们的定义如下:
- 记号 :表示预处理数组 的索引(十进制表示);
- 记号 :表示原始数组 的索引(十进制表示)。
我们通过以下的图,来看看 C1
、C2
、C3
、C4
、C5
、C6
、C7
、C8
分别是如何定义的。
上面的过程我们用如下的表来表示。
数组 C 的下标与数组 A 的下标的关系
- 伟大的计算机科学家注意到上表中标注了数组 C 中的元素来自数组 A 的元素个数,它们的规律如下:
- 将数组 C 的下标 表示成二进制,从右向左数,遇到 则停止,数出 的个数记为 ,则 的值 就是「数组 C 中的元素来自数组 A 的个数」,并且可以具体得到来自数组 A 的表示,即从当前下标 开始,从右向前数出 个数组 A 中的元素的和,即组成了
C[i]
。
- 将数组 C 的下标 表示成二进制,从右向左数,遇到 则停止,数出 的个数记为 ,则 的值 就是「数组 C 中的元素来自数组 A 的个数」,并且可以具体得到来自数组 A 的表示,即从当前下标 开始,从右向前数出 个数组 A 中的元素的和,即组成了
下面具体说明。
- 记号 :将 的二进制表示从右向左数出的 的个数,遇到 则停止,记为 。 我们只对数组 的索引 进行这个计算,数组 的索引 不进行相应的计算;
- 这里理解 是如何得到的是重点。
下面我们通过两个例子进行说明。
例 6
当 时,计算 。
- 分析:因为 的二进制表示是 ,从右边向左边数,第 个是 ,因此 的个数是 ,此时 。
例 7
当 时,计算 。
分析:因为 的二进制表示是 ,从右边向左边数遇到 之前,遇到了 个 ,此时 = 3。 计算出 以后, 立马得到,为此我们可以画出如下表格:
我们看到 是我们最终想要的。