為何只需改動兩個端點
設 為數值,且 。更新 對所有 的 加上 ,其中 。若最終陣列需要輸出之前已知道所有更新,逐個改動每個區間的每項可能重複大量工作。差分陣列記錄效果從何處開始及何處停止。
本課連繫前面的 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 前綴查詢,會得到 嗎?)
解答 · 答案
一般不會;它得到一個當前單點值。單點區間或偶然的數值相等可能吻合,但任意區間和需要額外推導或結構。