网格查询可能要求某个矩形区域的总和,一批更新则可能给多个矩形中的每格加值。每次都访问全部覆盖单元,会重复工作。前缀和压缩查询中的重复计算,差分网格则压缩更新中的重复计算。
两种方法都使用四个带符号的角,但存储含义不同。前缀项已经是一个区域的总和,差分项却是一条指令,必须累积后才产生作用。本节分别推导它们的符号和下标,而不是把记住一条公式当成解决两类问题的全部依据。
用边界定义网格矩形
定义 1.4.1
(左闭右开矩形与补边前缀表)
设 是整数网格,正高度为 、正宽度为 。查询边界 满足 、,所选单元的行下标为 、列下标为 。
定义大小为 的前缀表:
第零行与第零列全部为零。等于 或 的边界在表中合法,尽管不是 的单元下标。高度或宽度为零的矩形为空,总和为零。
参数顺序是上、左、下、右。左闭右开约定使高度为 、宽度为 ,在网格外边缘也成立。允许单元值为负;建立过程不要求前缀值递增。
用容斥建立一个前缀项
行 、列 的单元扩展上方与左方的前缀区域,它们的交集被计算了两次,因此
命题 1.4.2
(前缀递推式)
对 及 ,补边的表满足 ,而第零行与第零列均为零。
证明
(对扩大后的前缀作容斥)
新格上方的前缀覆盖行 之前、直到列 ;左侧前缀覆盖列 之前、直到行 。共同区域正是 ,减去它后,并集只计算一次,再加上 就得到目标前缀。
按行构造时,更早行的前缀和本行更早列的前缀都已算好。从零边界开始归纳,每项都具有定义中的求和含义。这一论证计算各格系数,对负数同样有效。 ∎
从四个前缀恢复任意矩形
答案是
第一项包含目标,也包含上方和左方区域。接下来两项移去这些区域,但它们共同的左上部分被移去了两次,所以最后加回一次。目标单元的净系数为一,其余单元为零。
若 或 ,四项自动成对抵消。这里没有读取原网格的哨兵单元;补边表存储的是边界位置代表的总和,因此查询可以恰好结束在网格高度或宽度。
定理 1.4.3
(四角矩形和)
对 及 ,、 范围内 的和,等于 。
证明
(每个格子的系数是一或零)
在 中,格子 的系数是 。因此在四角组合中,它的系数为
由于 ,第一个因子恰在 时为一,其余为零;由于 ,第二个因子恰在 时为一。所以目标格子的系数为一,其他格子的系数为零。当 或 ,有一个因子恒为零,便得到空和。∎
例题 1.4.4
(带正负值的网格与完整前缀表)
取
前缀表为:
| 行边界 a | P[a][0] | P[a][1] | P[a][2] | P[a][3] | P[a][4] |
|---|---|---|---|---|---|
查询 包含最后两行、列 1、2、3,其和为 。直接计算,两行分别贡献 和 。整个网格的和是 。
例题 1.4.5
(边缘条带与空矩形)
沿用上面的带正负值网格及其前缀表。整个网格 得 ,因为零行与零列为零。最后一列 得 ,与直接读取 相同。空矩形 有 ,所以其值为 ,不读取任何格子,也没有特殊情形。
常见错误
(把下边界与右边界当作包含在内)
边界是左闭右开的。要对带正负值网格的第 、 行及第 列求和,必须调用 。若传入最后包含的下标 ,只会选中第 行及第 列:,即 ,而不是 。
反例模式
四角思路不是前缀最小值的公式
考虑单行网格 与 。从原点开始的每个非空前缀,其最小值均为零,但最后一格查询的最小值分别是五和九。
所以前缀最小值数据甚至没有足够信息回答该查询。加法前缀能够相减,是因为贡献可以抵消;把总和换成最小值,不能保留同一论证。区间最小值结构需要不同的不变量。
反转视角,处理离线矩形加法
假设一次更新向矩形 的每格加整数 。使用大小为 的全零差分网格 ,写入四条指令:
这些是角标记,不是最终单元增量。全部更新完成后,对差分网格做两个维度的累积。单元 的增量,是所有 的 之和。
定理 1.4.6
(四个角标记加上一个矩形)
设 是大小为 的零网格;对每个更新 ,其中 ,,施行上面的四个标记改动。则对 的每个格子 ,(,)的总和,等于恰好那些矩形包含 的更新的 之和。
证明
(角脉冲与阶跃函数的乘积)
一条角指令对某格有贡献,当且仅当角的行、列下标分别不大于该格的行、列。用 表示条件 成立时为一,否则为零,则一次更新的四项贡献合计为
第一个因子恰在选中行区间内为一,第二个恰在选中列区间内为一,乘积便恰在矩形内部为一,外部为零。负增量适用同一代数;空矩形会使其中一个因子恒为零。
多个更新可以叠加,所以对合并标记累积,就得到全部指定增量之和。下、右标记可以安全存于边界 ,却不会给内部单元增加越过这些边界的贡献。 ∎
证明透视
标记证明依赖什么
不显而易见的一步,是把二维指示函数分解成行因子乘列因子,每个因子都是两个阶跃函数之差。这使四个正负号变成乘积:起始行配起始列为 ,起始配终止为 ,终止配终止又是 。代数运算完全不依赖格子本身,所以重叠、负的 与重复更新都由叠加原理推出。
假设 与 使每个因子成为指示函数。若 ,行因子在 的行上等于 ,那个“矩形”就会在这些行上减值。补出的第 行与第 列,只是让网格边缘的终止标记有地方存放; 的任何格子都不会读取它们,因为每个格子都有 及 。
例题 1.4.7
(重叠的正负增量)
在高三、宽四的全零网格上,执行 (0,1,2,4,+3)、(1,2,3,4,-2),恢复的增量网格为
第一个矩形有六格,总共增加 18;第二个有四格,总共增加 。最终总增量是十,按行也可得 。重叠部分的每格收到 。
下面的函数返回这个增量网格。若原网格非零,须把增量逐格加到原值;原网格并非角标记构造函数的输入。
例题 1.4.8
(结束于右下角的更新)
在同一个 网格上,对单个格子 加 ,即矩形 。标记为 、、、,后三个落在补出的第 行与第 列。格子 在 、 范围内只累积到 这个非零项,所以得到 。格子 的范围内没有非零标记,其他格子也是如此,所以其余增量皆为零。原值 (四角查询 得 )变成 。
重用前缀递推,但不要混淆下标
对 做包含当前格的二维累积,可以重用同一补边前缀函数。若 integrated = prefix_sums(D),原格 (i,j) 的增量就是 integrated[i+1][j+1],因为它包含差分下标不超过 的全部位置。
若读取 integrated[i][j],就漏掉第 行或第 列的标记,产生位移。中间差分网格多一个边界行、列,其前缀又多一个补边行、列。这只改变存储的常数因子,不改变原网格尺寸的含义。
概念视角代数
标记就是增量的混合差分
设 为增量格,用零扩充为 ,并在负下标处视为零。标记满足 ,即离散的混合二阶差分;对 作双重累加就恢复出 。四角查询则是反方向:矩形和就是前缀表 在矩形四个角上的混合差分。
def prefix_sums(grid):
if not grid or not grid[0]:
raise ValueError("a nonempty rectangular grid is required")
height, width = len(grid), len(grid[0])
if any(len(row) != width for row in grid):
raise ValueError("grid rows must have equal length")
prefix = [[0] * (width + 1) for _ in range(height + 1)]
for row in range(height):
for column in range(width):
prefix[row + 1][column + 1] = (
grid[row][column] + prefix[row][column + 1]
+ prefix[row + 1][column] - prefix[row][column]
)
return prefix
def rectangle_sum(prefix, top, left, bottom, right):
height, width = len(prefix) - 1, len(prefix[0]) - 1
if not (0 <= top <= bottom <= height and 0 <= left <= right <= width):
raise ValueError("rectangle boundaries must lie in the grid")
return (prefix[bottom][right] - prefix[top][right]
- prefix[bottom][left] + prefix[top][left])
def rectangle_additions(height, width, updates):
if height < 1 or width < 1:
raise ValueError("grid dimensions must be positive")
difference = [[0] * (width + 1) for _ in range(height + 1)]
for top, left, bottom, right, delta in updates:
if not (0 <= top <= bottom <= height and 0 <= left <= right <= width):
raise ValueError("rectangle boundaries must lie in the grid")
difference[top][left] += delta
difference[bottom][left] -= delta
difference[top][right] -= delta
difference[bottom][right] += delta
integrated = prefix_sums(difference)
return [[integrated[row + 1][column + 1] for column in range(width)]
for row in range(height)]
网格是包含整数单元的有限行序列;尺寸、边界和增量以整数为类型前提。代码检查正尺寸、非空矩形形状和边界,不验证整数类型。rectangle_sum 假设传入正确、未改变的前缀表,不在每次常数时间调用中验证任意表格。各函数均不修改原网格。
对带符号例子,rectangle_sum(prefix_sums(grid), 1, 1, 3, 4) 返回 9。rectangle_additions(3, 4, [(0,1,2,4,3),(1,2,3,4,-2)]) 返回所示增量。空矩形合法,但整个网格的高度或宽度为零,不在本实现的契约内。
常见错误
(读取积分表时早了一格)
设 integrated = prefix_sums(D)。在 网格上做单个更新 后,格子 应增加 ,它的值是 integrated[1][1],等于 。若读取 integrated[0][0],得到的是补边的零,更新就丢失了。
分清静态查询和批量更新
反例模式
旧前缀表不会自动观察后续更新
先为全零二乘二网格建前缀表,再把整个网格加一。旧前缀的整体查询仍返回零,更新后网格的总和却是四。
四次常数时间标记写入只描述更新,不会立即刷新全部可查询前缀。批量方法是在更新后累积标记,不是任意交错更新和查询的常数时间解法。不同工作负载需要重建,或使用有独立成本界限的动态结构。
建立静态前缀表需要 时间和存储单元。每个矩形查询只需 次访问和算术操作,所以包括预处理, 次查询总成本为 。
对于 次离线加法,标记写入需 ,恢复需 ,总计 时间、 存储单元。由于 ,常数数量的补边行、列不会改变这个界限。写出完整恢复网格本身也要 个输出。如果全部加法都早于查询,先恢复网格、加上原值,再为查询阶段建立新前缀表。
这些界限计算算术和单元数量。前缀值与累积标记的绝对值可能远大于单个输入,大整数也有位成本。Python 整数保留精确结果;定宽实现必须保留中间加减以及最终答案。公式依赖的是加法抵消,不是非负性或表格单调性。
练习与详解
快速检查
(1. 计算带负数的矩形)
对显示的带符号网格,分别用四个前缀和直接加六格,计算 (1,1,3,4)。哪一项给出整个网格的总和?
解答 · 解答 1
四项为 ,选中两行的和为四、五,也共九。整体总和是 。负数不会破坏抵消证明。
快速检查
(2. 区分空矩形与无效边界)
为什么上边界等于下边界时查询为零,下边界却可以等于 H?这为什么不允许访问原网格的第 H 行?
解答 · 解答 2
相同行边界使四项抵消,而且没有被选行。下边界 在补边前缀表中有表示,包含下标小于它的原行,直到 。原单元下标仍止于 ;前缀边界不是原单元。
快速检查
(3. 按符号设置四个更新角标记)
给 (0,1,2,4) 加三,四个标记如何改变?为什么差分网格必须支持列边界四?哪个累积项恢复原单元 (0,1)?
解答 · 解答 3
在 、 加三,在 、 减三。原列虽止于三,右边界仍为四,因此差分网格包含该边界列。原单元 (0,1) 由 integrated[1][2] 恢复,才能包含 的标记。
快速检查
(4. 按面积和逐格结果核验重叠增量)
对两项例题更新,一个重叠格得到多少增量?整体增量是多少?返回数组是否已经包含原有非零值?
解答 · 解答 4
重叠格得到 。总量为 ,与恢复后的行和 一致。返回数组只有增量,需要时再逐格加到原网格。
快速检查
(5. 声称常数操作前,先确定工作负载)
为什么四次标记写入不会使旧前缀表上的后续查询正确?若所有更新先完成、之后才开始查询,可以怎样处理?
解答 · 解答 5
旧前缀存储旧值总和,标记尚未累积到它的各项。先更新后查询时,可恢复全部增量、加入原值,再建立新前缀表。任意交错需要额外维护,不能从两个分开阶段直接继承常数更新与查询的结论。
快速检查
(6. 分清代数、存储单元和输出成本)
为什么总和能用四角相减,最小值却不能替换进同一证明?为什么 单元和每次常数算术,不自动意味着相同的位复杂度?
解答 · 解答 6
加法贡献有逆元,可以抵消;最小值没有保存被移除区域的信息,、 已说明这一点。保存的和可能比单格需要更多位,大整数算术也有成本。恢复整个网格还需写出 项,尽管每次标记更新只进行了四次写入。