前綴和能迅速回答區間總和,是因為輸入固定。若兩次查詢之間數值改變,舊前綴仍然描述舊陣列。每次更新後全部重建是正確做法,卻可能每次都花線性時間。我們需要一種表示方法,令改動之後,大部分已儲存資訊仍然有用。
把陣列分成大小適中的區塊,就有一種這樣的方法。查詢在兩端逐項掃描,對中間完整覆蓋的區塊則直接使用一個總和。區間加法沿用相同分割:兩端改個別項目,完整區塊只記下延後加量。後來若有操作只觸及該區塊的一部分,這個延後加量的含義仍須保持精確。
我們會按輸入次序處理操作,不重排查詢,也不假設所有更新都先於查詢。這與 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. 指定用新值與舊邏輯值的差
舊值是 ,增量因此是 。基值變成 ,延後加量仍為 ,區塊總和變成 。查詢兩個邊界項目仍為 及 ,所以答案是 。若直接寫入基值 ,表示的是 ,並非要求的 。