为何只需改动两个端点
设 为数值,且 。更新 对所有 的 加上 ,其中 。若最终数组需要输出之前已知道所有更新,逐个改动每个区间的每项可能重复大量工作。差分数组记录效果从何处开始及何处停止。
本课联系前面的 Fenwick 树和线段树课文。假设算术和数组访问均为常数时间,数值表示可精确处理所有和而不溢出。
不变量
定义 4.1.1
(差分数组与哨兵)
使用索引 。令 、当 时 ,额外的哨兵取 。对每个实际位置 ,原值由望远镜求和得到:
哨兵不属于重建后的数组。要在 加上 ,只改动
这也适用于 :第二次变更落在 ,不包含于任何实际前缀。哨兵初始化为零只是记账选择;它无须等于涉及假想 的差。
命题 4.1.2
(以两个端点变更完成区间加法)
设 为上述差分数组, 为满足 的更新。把 改为 ,把 改为 。则对每个 ,前缀和 在 时增加 ,其余情况不变。因此,经过任意有限次这样的更新后, 的前缀和等于直接逐项执行这些更新所得的数组。
证明
(前缀和只在 l 与 r 之间看到变化)
对位置 ,前缀和的变化是
这验证一次更新对每个位置的效果。重复此论证或把增量相加,可证任意有限次更新后不变量仍成立,包括重叠区间及负增量。
证明透视
论证在何处用到两个端点
关键而不明显的一步,是把区间写成两个阶梯函数之差: 使效果对之后每个前缀生效, 再把它关掉。由于 本身包含在内,抵消的阶梯应从区间之后的第一个位置,即 开始,而不是从 开始。
假设 保证抵消阶梯在起始阶梯之后,所以两者之差确实是 的指示函数。当 时,抵消阶梯不会被任何实际前缀看到,这正是需要哨兵 的原因。其余由线性性完成:每个更新各自独立贡献,重叠或负增量都无须分情况讨论。论证从头到尾没有用到 的值。
处理完全部更新后,对 从左至右做一次前缀扫描,输出最终 。初始化差分及重建均需 , 次更新需 ,所以总时间为 ,额外数组占 空间。这是离线界:若每次更新后都输出全部 个当前值,还需额外输出工作。
跟踪例子
例题 4.1.3
(五项上的两个重叠更新)
初始 ,所以 。先在 加 ,再在 加 。端点变更得到
前五个前缀和为 ;直接对 做两次更新也得相同结果。第六项是哨兵,不是第六个输出值。
例题 4.1.4
(结束于最后位置的更新)
仍用 ,在 加 。此时 ,第二次变更落在哨兵:,,得 。前五个前缀和为 ,即 的最后一项增加 。哨兵 从不属于输出的前缀。
例题 4.1.5
(内部的单一位置)
取 ,所以 。在 加 ,变更为 、,得 。前缀和为 ,只有 由 变为 。原本 这类零项表示“与前一项相同”,并不表示“值为零”。
常见错误
(把差分项当作数组的值)
在跟踪例子第一次更新后,差分数组是 ,而数组是 。 只表示 比 小 ,并不是 。读取数值之前必须先对 取前缀和。
常见错误
(只分配 n 个差分位置)
当 时,更新会写入 。若数组只有 个位置,在检查边界的语言中这次写入会越界,在不检查的语言中则会悄悄破坏相邻内存。即使只输出前 个前缀和,也应分配 个位置。
反例模式
在 r 而非 r+1 停止
断言:要在 上加 ,就在 加 、在 减去 。取 ,故 ,并在 上加 。按此断言得 ,前四个前缀和为 ;但该更新应得 ,位置 被漏掉。对单点区间 ,两次变更甚至落在同一差分项上互相抵消,完全没有改动。由于 本身包含在区间内,抵消的变更应放在 。
在线单点值
若区间加法和单点查询交错进行,可用前一课的 Fenwick 树存储 。每次区间加法变成两次单点加法;查询 则是 Fenwick 前缀和 。包含哨兵的树有 个位置。在前一课的假设及常数时间算术下,每次更新或单点查询需 。一基查询不会把哨兵当成实际数组位置。
这棵树支持区间加法和单点值,并不会自动以一次前缀查询给出当前 的区间和;后者是另一种操作,需要进一步结构或计算。应按操作契约选方法,而不是只因为熟悉某棵树。
习题与解答
快速检查
(最后位置。对 的更新改动哪些差分项?)
解答 · 答案
加 , 减 ;唯一受影响的实际前缀在 。
快速检查
(抵消。同一区间先加 再加 会怎样?)
解答 · 答案
两端变更均抵消,因此每个重建值恢复原状。
快速检查
(跟踪核对。例子第一个更新后, 是多少?)
解答 · 答案
更新后前四个差分项 之和为 ;也即 。
快速检查
(操作范围。对 做一次 Fenwick 前缀查询,会得到 吗?)
解答 · 答案
一般不会;它得到一个当前单点值。单点区间或偶然的数值相等可能吻合,但任意区间和需要额外推导或结构。