網格查詢可能要求一個矩形區域的總和,一批更新則可能替很多矩形的每個格子加值。逐格處理每次覆蓋會重複工作。前綴和壓縮查詢中的重複計算,差分網格則壓縮更新中的重複計算。
兩種方法都使用四個帶正負號的角,但儲存含義不同。前綴項目已是一個區域的總和;差分項目卻是一項指令,要累積後效果才出現。本節會分別推導符號與下標,而不是以為記住一條公式就足以處理兩個問題。
用邊界定義網格矩形
定義 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
加法貢獻有逆元可抵銷;最小值不保留被移除區域的資訊,、 已示範此事。儲存總和可能比單格需要更多位元,大整數算術也有成本。恢復整個網格還要輸出 項,即使每次標記更新只用四次寫入。