数值会改变时,问题有什么不同?
设 是整数数组,。我们要交错执行两种操作:把某个 增加整数 ,以及查询连续区间 的和。逐项重算区间最多要做 次加法。前缀和数组可加速查询,因为
但改变 就会改变 。普通前缀和数组因此以可能需要线性时间的更新,换取常数时间查询。 树状数组,亦称二叉索引树或 Fenwick 树,改为存储特定区间的和,使查询和更新都只需访问对数数量的存储区间。“树”描述的是数组索引之间的关系,实现并不需要指针节点。
本节全部采用从一开始的索引,数学推导使用精确整数运算。程序须选择足以容纳累积结果的数值类型;单一项很小,不代表整段总和也小。
一个树节点究竟存储什么?
定义 1.1.1
(最低有效位与其存储区间)
对正整数 ,令 是整除 的最大二次幂。若 且 为奇数,则 。树的不变量是
以 表示这个包含两端的索引区间。
例如 的 lowbit 是 ,故 存储索引 的和。
lowbit 是区间长度,不是左端点。一般固定位数的二进制表示可用 i & (-i)
计算正索引的 lowbit:在二进制补码取负运算中,最低的非零位保留下来,它上方的比特则反转,所以按位 AND 只留下这一位。上面的数学定义不依赖程序语言的表示规则。
例题 1.1.2
(八项数组的全部存储区间)
从以下数组开始:
| 存储区间 | |||
|---|---|---|---|
这些区间有重叠。查询必须挑出互不相交的一组;把所有存储项相加,会重复计算部分原值。
前缀查询:每次取走一个完整区块
要算 ,先取以 结束的区块,剩下的就是终点为 的前缀,再重复同一步。
PREFIX(r): // precondition: 0 <= r <= n
total = 0
i = r
while i > 0:
total = total + T[i]
i = i - lowbit(i)
return total
RANGE_SUM(l, r): // precondition: 1 <= l <= r <= n
return PREFIX(r) - PREFIX(l - 1)
命题 1.1.3
(以完整区块做前缀查询)
对 ,PREFIX(r) 返回 。它加上由 反复减去 lowbit 所得各下标 的 ,而对应区块 两两不相交,并集为 。
证明
(前缀查询为什么不漏项,也不重复?)
以 表示原来的查询终点。在每轮开始时保持
初时 total 为零,。 正是剩余前缀的最后 项;把它加进 total,再令 变成 ,等式仍成立。因 lowbit 为正,非负索引严格下降,最后到达零。剩余总和此时为空和,所以返回的 total 恰是 。每个选取区块紧接在下一个剩余前缀的右方,这同时证明了完整覆盖及互不重叠。
此例中 PREFIX(7) 访问 ,返回 。所选区间是 、、,虽由右往左处理,并集恰好是 。
PREFIX(0) 立即返回零,并不读取 。
概念视角代数
从长度的二进制展开读出前缀
把 写成 ,其中 。逐次减去 lowbit 正是按这个次序移除这些 2 的幂,所以 PREFIX(r) 的各个区块长度为 ,从 的右端开始读。例如 ,长度为 ,区块是 、、。这个查询就是把整数 拆成二进制数位,再用到区间上。
单点加法:改变每个包含该点的存储区块
若 增加 ,一个存储区间的和会增加 ,当且仅当它包含 。其他存储区间必须保持不变。更新路径恰好列出所有包含该点的区间:
ADD(p, delta): // precondition: 1 <= p <= n
i = p
while i <= n:
T[i] = T[i] + delta
i = i + lowbit(i)
伪代码的索引是数学整数。实现时,计算下一个索引的加法必须可表示,包括最后一次跳出 的运算。
命题 1.1.4
(更新路径恰好触及包含该点的区块)
对 及整数 ,循环 ADD(p, delta) 对每个满足 的 恰好把 加到 一次,其他项不变。之后,树的不变量对“ 换成 ”的数组成立。
证明
(更新路径为什么恰好找出全部受影响区块?)
第一个区块 包含 。假设目前索引 的 lowbit 是 ,令 。因 为奇数, 可被 整除,所以
因此 包含整个 ,当然也包含 。这证明了每个访问区块都确实需要更新。
还须证明没有漏掉其他受影响区块。任何包含 的区块,其终点至少是 。对两个相继访问的索引 、,考虑它们之间的 ,其中 。 的最低 位都是零,故 ,从而
所以 的起点严格大于 ,不能包含 。第一个终点 之前没有候选;上述推理又排除了每段路径间隙,包括下一个终点超过 时的最后间隙。因此每个受影响区块恰好更新一次,单点加法后重新满足存储不变量,供之后每次查询使用。
证明透视
查询与更新的路径回答不同问题
更新证明的关键一步,是当 为奇数时, 能被 整除。加上 lowbit 会向更高的位进位,所以下一个区块严格更长,并包含上一个区块。这种嵌套,正是被访问的区块恰好构成包含 的区块链的原因。查询证明用的是相反的结构:减去 lowbit 后,剩下的前缀恰好结束于被取走区块的开始处,所以区块互不相交,而不是互相嵌套。
仅靠嵌套只能说明每个被访问的区块都受影响。要说明没有漏掉,必须用另一个间隙论证:对 ,, 的 lowbit 等于 的 lowbit,所以 开始于 之后。界限 只用来停止循环,在两个论证中都不起作用。两个循环正负号相反,是这两个不同不变量的结果,而不是要死记的公式。
例题 1.1.5
(更新一项,再核对区间查询)
从八项原数组执行 ADD(5, 2)。更新访问 ,再到树外的 。改变的节点是
其他 不变。现在 PREFIX(7) 得 ,所以
直接计算,改后的区间为 ,其和确实是 。更新位置 不应修改 ,因为 没有包含该位置。查询路径 与更新路径 虽有共同索引,却不能互相代替。
例题 1.1.6
(大小不是二的幂的情形)
取 ,每个 ,所以 ,例如 ,,。执行 ADD(9, 3)。路径是 :lowbit 为 使 变成 ,lowbit 为 使 变成 ,lowbit 为 使 变成 ,超过 ,循环停止。所以 ,,。(区间 )与 (区间 )不含位置 ,保持不变。之后 PREFIX(13) 经过 ,返回 ,结果正确。
常见错误
(把 lowbit 当作区块的起点)
对 ,lowbit 是 。若把 当作区块起点,就得到 ,共九项,这是错的。lowbit 是区块的长度:,。
常见错误
(加上新值而不是变化量)
要在八项数组上把 设为 ,调用 ADD(5, 2) 会使 、,因为原来 。所需的变化量是 ,这样 。ADD 永远是加上,不是设置。
在带正负数的数据上追踪不变量
上面的例题使用正数数组。下图另选两个固定数组,其中含负数;这是新例子,不是接着上一个更新。每次选择操作,都从所选数组重新开始。画面的目标数组表示增量操作要达到的结果,即使部分树项仍待更新,目标仍会先列出。
存储区间由索引决定,与数值的正负无关。非空区间的和可以为零;若它属于查询的分解,仍须读取。同样地,增加零也要访问受影响项目,只是没有数值改变。请分开观察访问进度与是否等于目标值。
先追踪前缀查询,再比较单点增量:减去 lowbit 会取走已完成的查询区块,加上 lowbit 则找下一个包含更新位置的区块。两条路径证明的事情不同。空查询 prefix(0) 合法;位置零的更新却不合法。
为什么两种操作都是对数时间?
命题 1.1.7
(两种操作的对数成本)
设 。对 ,PREFIX(r) 至多迭代 次。对 ,ADD(p, delta) 至多访问 个下标。树存储 个和。
证明
(清除位与 lowbit 倍增)
查询时减去 lowbit,会清除索引最低的一个非零位。因此循环次数等于原索引 的非零位数;当 ,最多是 。更新时,下一索引的 lowbit 至少是目前的两倍,上面的证明已说明这一点。每个有效索引的 lowbit 不超过 ,所以访问次数同样最多为 。更新的索引本身未必加倍: 的下一站是 ,不是 ;至少加倍的是 lowbit。∎
树存储 个区间和,空间为 。从零树开始,对每个 做
ADD(i, a_i),便可在 时间建立不变量。这是正确的简单构造法,并非断言不存在线性时间构造法。上述证明亦无须 为二次幂:若 ,PREFIX(13) 的路径是 ,而位置 的更新仍经过 ,然后离开索引范围。
增量、赋值,以及前缀相减背后的代数
ADD(p, delta) 是增加一个变化量,不是把 设成该参数。若要赋值为 ,应计算 ,执行加法;若另有保留原数组,也要记录 。没有原数组副本时,可用 RANGE_SUM(p, p) 在对数时间取得旧值。例如在原数组把 设为 ,所需变化量是 ,不是增加 。结果 分别变成 。负数项及负增量都符合区间和的不变量。
反例模式
把和换成最小值,并不能沿用这些公式
数组 与 在终点 、 的前缀最小值都同为 ,但它们在 上的最小值分别是 、。所以这两个前缀最小值不能决定任意区间最小值;不存在像减去前缀和那样,把较早部分的最小值“撤销”的运算。
更新也不同。若存储区间包含 ,其最小值为 ;把第一项增加至 后,新最小值是 。若只取旧存储值 与新值 的较小者,便错误保留了 。受限制的最小值查询变体须有自己的不变量及更新假设;本节无限制加法的证明并不适用。
练习与完整解答
每题均重新使用最初的八项数组。
快速检查
(PREFIX(6) 使用哪些项?写出其存储区间。)
解答 · 答案
路径是 ,选取 与 ,答案是 。
快速检查
(执行 ADD(3, -4),哪些树节点改变?新的 RANGE_SUM(3, 7) 是多少?)
解答 · 答案
更新路径是 ,得到 。原来 的和为 ,新值为 。查询也得到同一结果:PREFIX(7) 为 ,PREFIX(2) 为 ,所以 。
快速检查
(若以 调用更新循环,为什么不会前进?)
解答 · 答案
lowbit 的正索引定义不适用于零。即使程序的位运算在零得到零,下一个索引仍是零,造成无限循环。外部从零开始的位置 ,须先转成内部位置 。
快速检查
(把 设为 ,求 PREFIX(7),并解释更新参数为什么是负数。)
解答 · 答案
变化量是 ,所以 PREFIX(7) 变成 。若增加 ,原项会变成 ,处理的是另一个问题。
实现比较及其他变体可参阅 CP-Algorithms 的 Fenwick 树文章。