前缀和能够快速回答区间总和,是因为输入固定。如果两次查询之间数值发生变化,旧前缀仍在描述旧数组。每次更新后全部重建当然正确,却可能每次都花费线性时间。我们需要一种表示方式,使一次改动之后,大部分已存信息仍然有用。
把数组分成大小适中的块,就得到一种这样的方式。查询逐项扫描两端,用一个存储总和处理每个完整覆盖的中间块。区间加法采用相同划分:两端修改各个元素,完整块只记录延迟加量。之后若有操作只涉及该块的一部分,这个延迟加量的含义仍须保持精确。
我们按输入顺序处理操作,不排序查询,也不假设所有更新都先于查询。这与 Mo 算法使用平方根的方式不同;Mo 的静态输入和可逆移动区间,分别需要不同的不变量。
区分逻辑数组与存储表示
设 是整数数组,。区间采用半开形式: 包含下标 ,其中 。特别地,允许 ,表示空区间。整数增量 的加法把区间内每项改为 ;查询返回区间总和,空和定义为零。
选择块大小 。块 的起点为 ,终点为 ,实际长度为 。非空块共有 个。最后一块可能短于 。
定义 1.5.1
(基值、延迟加量与真实总和的不变量)
每个下标存储基值 ;每块存储延迟加量 及总和 。它们的含义为
因此 是逻辑元素的总和,不只是存储基值的总和。初始化时,把输入复制到 ,所有 设为零,并把各块输入元素相加得到 。
基值数组只是实现中的表示。整块加法之后,单独读取 不一定得到当前数值。
推导两种更新规则
若加法完整覆盖一块,保持基值不变,只令
每个逻辑元素增加 ,总和为该块的 个元素各增加一次。无论块有多长,都只需常数工作。
若加法只覆盖某块的子集 ,保留 ,对每个 的 加上 ,并把 增加 。共同的延迟加量不变,因此修改选中的基值已足以改变所需逻辑元素。不必先把旧延迟加量分发给整块所有基值。
命题 1.5.2
(延迟块不变量得以保持)
从已初始化的结构开始,每次加法都按上面两条规则处理:完整块改变 与 ,部分块改变被选基值与 。则经过任意有限次加法后,对所有 有 ,并且每个块都有 。
证明
(每条规则恰好改变一项)
更新前,选中元素为 。把基值改为 后,它变为 。未选中的基值与延迟加量都不变,所以其余逻辑元素不变。
基值总和增加 ,而 不变。因此把 恰好增加 ,便恢复不变量中的两个等式。整块规则则改变第二项,同样满足等式。初始化与这两种情况共同证明,任意有限次加法之后,不变量都成立。 ∎
证明透视
延迟块的证明依赖什么
不显而易见的一步,是不变量针对的是和 ,而不是其中任何一项。部分更新从不需要把 分发给各个基值:它只改变一个加项,另一个加项仍然有效。整块更新则改变另一个加项。每条规则之所以正确,是因为它恰好改动两项中的一项;这也说明为何两项都改会把 算两次。
承担重任的假设是可加性:把块的每一项平移 ,其总和平移 ,其中 是该块的实际长度。正因如此, 才能以常数时间更新。对最小值或最大值,这个事实并不成立,因为它们只移动 ,而不是 。证明是对操作序列的归纳,没有用到块大小或 的正负。
查询总和时,完整块贡献 ;部分覆盖的块则逐项读取 。这些贡献必须把 分成互不相交的部分,否则即使块总和正确,仍可能被重复计算。
概念视角代数
把加法与查询看成向量运算
设 为该区间的指示向量。逻辑数组是 ;一次加法就是把 加到 上;一次查询则是点积 。这个指示向量可以拆成若干完整块的指示向量之和,再加上至多 个单项指示向量。前一部分由块标量 与 处理,后一部分逐项处理。
跟踪两个带延迟加量的块
例题 1.5.3
(完整中间块与较短末块都能采用延迟加法)
取 、,并令
三个块是 、、,初始总和为 ,延迟加量为 。对 加 。第一块只修改下标 2、3;另外两块均被完整覆盖,包括长度只有二的末块。
| 块 | 加法后存储的基值 | 延迟加量 | 真实总和 |
|---|---|---|---|
逻辑数组现在为 。查询 时,取下标 3 的逻辑元素、完整中间块和下标 8 的逻辑元素,得到 。
接着对 加 。中间块基值变为 ,延迟加量仍为 ,总和由 降为 。其逻辑元素为 。再次查询 ,得到 。
反例模式
延迟加量既不能丢失,也不能计算两次
假设某块基值为 ,延迟加量为 ,总和为 ,所以逻辑元素为 。只给首项加 ,应得到 。把基值改为 ,保留延迟加量 ,总和改为 即可。
若没有先把延迟加量加进每个基值,就直接将其清零,表示的数值将变成 。若整块加法同时增加每个基值和延迟加量,每个逻辑元素就收到两次增量。每种更新规则都应只改变 中的一项。
不用额外端点分支来划分区间
从 开始。令 为 所在块,并计算其真实终点 。若 且 ,整块都在剩余区间内;处理该块,再把 推进到 。否则只处理下标 ,然后把 加一。
命题 1.5.4
(划分循环恰好消耗指定区间)
对 ,从 开始的循环处理若干互不相交的片段,每个片段是单个下标或完整块,其并集为 ,循环在 时停止。
证明
(已处理的前缀)
每次迭代开始时,已处理下标恰为 ,没有处理该区间外的元素。整块分支消耗 ;由 和 ,它位于要求的 内。逐项分支消耗 ,而循环要求 ,故它也位于要求之内。
两个分支都在已处理前缀之后添加一个非空区间,既不重叠,也不跳过元素。它们都严格增加 ,但不会越过 。在 时终止,便得到互不相交的完整划分。空区间不进入迭代,因此 也不需要查找任何块。 ∎
例题 1.5.5
(两个端点在同一块内,以及空区间)
再从 、 开始,对 加 。在 ,块是 而 ,所以只处理下标 ;下标 同理。两个基值改变,成为 与 ,延迟加量保持 ,块总和增加 ,由 变成 。查询 取整个块,返回 ,等于 。查询 使用三个块总和 、、,返回 。空查询 不进入任何迭代,所以不查块就返回 。
部分覆盖的块至多两个:左端点所在块,以及最后一个被包含下标所在块。严格处于两者之间的块都完整覆盖。若两端在同一块,该块只扫描一次。循环中的整块判断也能识别完整的短末块;若只测试 i + B <= r,就无法识别这种情况。
可执行实现
实现假设输入值、增量和下标都是整数。它拒绝空数组及非法边界,但接受空操作区间。构造函数复制输入,因此操作不会修改调用者的列表。
from math import isqrt
class SqrtRangeAddSum:
def __init__(self, values):
self.base = list(values)
self.n = len(self.base)
if self.n == 0:
raise ValueError("the array must be nonempty")
self.size = isqrt(self.n - 1) + 1
count = (self.n + self.size - 1) // self.size
self.lazy = [0] * count
self.total = [0] * count
for i, value in enumerate(self.base):
self.total[i // self.size] += value
def _bounds(self, left, right):
if not 0 <= left <= right <= self.n:
raise ValueError("invalid half-open range")
def add(self, left, right, delta):
self._bounds(left, right)
i = left
while i < right:
block = i // self.size
end = min(self.n, (block + 1) * self.size)
if i == block * self.size and end <= right:
self.lazy[block] += delta
self.total[block] += (end - i) * delta
i = end
else:
self.base[i] += delta
self.total[block] += delta
i += 1
def sum(self, left, right):
self._bounds(left, right)
answer = 0
i = left
while i < right:
block = i // self.size
end = min(self.n, (block + 1) * self.size)
if i == block * self.size and end <= right:
answer += self.total[block]
i = end
else:
answer += self.base[i] + self.lazy[block]
i += 1
return answer
def assign(self, index, value):
if not 0 <= index < self.n:
raise IndexError("invalid array index")
block = index // self.size
delta = value - (self.base[index] + self.lazy[block])
self.base[index] += delta
self.total[block] += delta
正整数 的 isqrt(n - 1) + 1 等于 ,对完全平方数也成立。代码没有使用浮点平方根。Python 整数算术是精确的;下面统计整数算术步数,而非任意长整数的位操作成本。
赋新值 时,旧逻辑值为 ,所以所需增量为 。对这一项应用部分更新规则,就使它恰好等于 。直接把基值设为 ,表示的反而是 。
例题 1.5.6
(部分更新之后的赋值仍保留原有延迟状态)
延续十项示例中的两次加法。下标 6 的基值为 ,延迟加量为 ,所以当前逻辑值为 。把它赋为 ,改变量为 。其基值变为 ,而块的延迟加量仍为 ,总和由 降到 。
中间块现在表示 ,总和确实为 。因此查询 返回 。其余元素,包括共享同一延迟加量的元素,都保留原值。
平方根从何而来
命题 1.5.7
(区间加法与求和的成本)
对块大小 ,区间加法或区间求和在最坏情况下耗时 ,因此当 时为 。初始化耗时 ,单点赋值耗时 。
证明
(边界项与完整块)
对一般块大小 ,一次区间操作至多处理两个部分块,每个逐项处理至多 个元素,另处理至多 个完整块。在算术步数模型中,每次迭代只做常数工作。因此区间加法和区间总和的最坏时间均为
初始化需要 时间;基值和块数组使用 个存储单元。在这种表示中,单点赋值需要 时间。代码取 ,块数至多为 ,因此每次区间操作为 。 ∎
这个界适用于任意交错操作,不依赖均摊平均。它也没有说每个请求都耗费平方根时间:完整一块只需一次迭代,空区间需要常数时间。太小或太大的块,都会让一类工作便宜而另一类工作昂贵。
反例模式
真实总和必须使用实际块长度
当 、 时,最后一块只有两个元素。对完整末块加 ,总和应增加 ,不是 。若用名义大小 更新总和,即使逐项读取的逻辑值仍然正确,整块查询也会回答错误。只保证单项数值正确,并不能证明总和不变量。
常见错误
(把基值当作当前的值)
在追踪中对 加 后,基值 仍是 ,但逻辑值是 。基值数组只是实现细节。只要延迟加量非零,单读 就会得到错误的值;必须加上该块的延迟加量。
常见错误
(用整数除法计算块数)
对 、,块的起点是 ,所以共有 个,最后一个只有一项。若把数目算成 ,块记录就分配得太少,下标 所属的块并不存在。应使用上取整 。
方法依赖加法与总和的代数性质:共同增量 让块总和增加块长度乘以 。其他聚合量或更新需要各自的不变量。例如,整块最小值只增加 ,不是 ;其部分更新也不能使用总和规则。把整块全部替换为某个值,同样需要不同的延迟操作设计。
练习与完整解答
快速检查
(1. 十项示例对 [2,10) 加 3 后,中间块的基值总和只有 4,为何块总和为 16?计算 。)
解答 · 1. 延迟贡献恰好加入一次
中间块长四,基值总和为 ,延迟加量为 。真实总和是 。两个边界元素的逻辑值为 和 ,所以请求的总和是 。若再把延迟贡献加入已存的总和,就会重复计算。
快速检查
(2. 某块基值为 [2,3]、延迟加量为 4、总和为 13。只给首项加 -5。写出新的全部存储量和两个逻辑值。)
解答 · 2. 负的部分加法保留延迟标记
新基值是 ,延迟加量仍为 ,总和变为 。逻辑元素为 ,总和为 。未改变的第二个基值与共同延迟加量,使第二项保持不变。
快速检查
(3. 短末块的基值为 [5,3]、延迟加量为零、总和为 8。对完整块加 3,为何新存储总和 20 是错误的?)
解答 · 3. 计算真实项数,而不是名义容量
只有两项,因此延迟加量变为 ,总和变为 ,逻辑元素为 。错误值 把块长度当成四:。它计入数组外两个位置,破坏了总和等式。
快速检查
(4. 程序员处理部分更新时,先修改选中基值,再把整块延迟加量清零。用基值 [1,2]、延迟加量 5 展示错误。额外做什么才可合法清零?)
解答 · 4. 清除延迟加量前须把它实际写入所有基值
只给第一个逻辑元素加 ,应把 改成 。若先把首个基值改成 就清零延迟加量,表示的却是 。合法做法是先给每个基值加 ,得到 ,再清零延迟加量并执行部分修改,得到基值 和总和 。该方法正确,却需要扫描整块;保留延迟加量能够避免这部分额外工作。
快速检查
(5. 为什么 B=1 与 B=n 都允许最坏情况为线性时间的区间操作?B=n 时查询整个数组总和只需常数时间,是否与界矛盾?)
解答 · 5. 完整块处理与边界扫描都必须计入
时,查询整个数组要处理 个完整单项块。 时虽然只有一块,但当 ,区间 会逐项扫描 项。因此随着 增大,两个极端都无法保证次线性的最坏区间操作。 的全数组查询只取一个总和,确实只需常数时间;最坏情况上界不必由每个请求达到。
快速检查
(6. 示例两次加法后,下标 6 的基值为零、延迟加量为 3、块总和为 12。把其逻辑值赋为 -4。求新基值、块总和与 。)
解答 · 6. 赋值使用新值与旧逻辑值之差
旧值为 ,因此增量为 。基值变为 ,延迟加量仍为 ,块总和变为 。查询的两个边界元素仍为 和 ,所以答案为 。若直接写入基值 ,表示的将是 ,并非请求的 。