數值會改變時,問題有甚麼不同?
設 是整數陣列,。我們要交錯執行兩種操作:把某個 增加整數 ,以及查詢連續區間 的和。逐項重算區間最多要做 次加法。前綴和陣列可加速查詢,因為
但改變 就會改變 。普通前綴和陣列因此以可能需要線性時間的更新,換取常數時間查詢。 二元索引樹,亦稱 Fenwick 樹,改為儲存特定區間的和,使查詢和更新都只需探訪對數數量的儲存區間。「樹」描述的是陣列索引之間的關係,實作並不需要指標節點。
本節全部採用從一開始的索引,數學推導使用精確整數運算。程式須選擇足以容納累積結果的數值類型;單一項很小,不代表整段總和也小。
一個樹項目究竟儲存甚麼?
定義 1.1.1
(最低有效位與其儲存區間)
對正整數 ,令 是整除 的最大二次冪。若 且 為奇數,則 。樹的不變量是
以 表示這個包含兩端的索引區間。
例如 的 lowbit 是 ,故 儲存索引 的和。
lowbit 是區間長度,不是左端點。一般固定位數的二進位表示可用 i & (-i)
計算正索引的 lowbit:在二補數取負運算中,最低的非零位保留下來,它上方的位元則反轉,所以逐位 AND 只留下這一位。上面的數學定義不依賴程式語言的表示規則。
例題 1.1.2
(八項陣列的全部儲存區間)
從以下陣列開始:
| 儲存區間 | |||
|---|---|---|---|
這些區間有重疊。查詢必須挑出互不相交的一組;把所有儲存項相加,會重複計算部分原值。
前綴查詢:每次取走一個完整區塊
要算 ,先取以 結束的區塊,剩下的就是終點為 的前綴,再重複同一步。
PREFIX(r): // precondition: 0 <= r <= n
total = 0
i = r
while i > 0:
total = total + T[i]
i = i - lowbit(i)
return total
RANGE_SUM(l, r): // precondition: 1 <= l <= r <= n
return PREFIX(r) - PREFIX(l - 1)
命題 1.1.3
(以完整區塊作前綴查詢)
對 ,PREFIX(r) 傳回 。它加上由 反覆減去 lowbit 所得各索引 的 ,而對應區塊 兩兩不相交,並集為 。
證明
(前綴查詢為甚麼不漏項,也不重複?)
以 表示原來的查詢終點。在每輪開始時保持
初時 total 為零,。 正是剩餘前綴的最後 項;把它加進 total,再令 變成 ,等式仍成立。因 lowbit 為正,非負索引嚴格下降,最後到達零。剩餘總和此時為空和,所以傳回的 total 恰是 。每個選取區塊緊接在下一個剩餘前綴的右方,這同時證明了完整覆蓋及互不重疊。
此例中 PREFIX(7) 探訪 ,傳回 。所選區間是 、、,雖由右往左處理,並集恰好是 。
PREFIX(0) 立即傳回零,並不讀取 。
概念視角代數
從長度的二進位展開讀出前綴
把 寫成 ,其中 。逐次減去 lowbit 正是依此次序移除這些二的冪,所以 PREFIX(r) 的各區塊長度為 ,從 的右端起讀。例如 ,長度為 ,區塊是 、、。這個查詢就是把整數 拆成二進位數字,再應用到區間上。
單點加法:改變每個包含該點的儲存區塊
若 增加 ,一個儲存區間的和會增加 ,當且僅當它包含 。其他儲存區間必須保持不變。更新路徑恰好列出所有包含該點的區間:
ADD(p, delta): // precondition: 1 <= p <= n
i = p
while i <= n:
T[i] = T[i] + delta
i = i + lowbit(i)
偽代碼的索引是數學整數。實作時,計算下一個索引的加法必須可表示,包括最後一次跳出 的運算。
命題 1.1.4
(更新路徑恰好觸及包含該點的區塊)
對 及整數 ,迴圈 ADD(p, delta) 對每個滿足 的 恰好把 加到 一次,其他項目不變。之後,樹的不變量對「 換成 」的陣列成立。
證明
(更新路徑為甚麼恰好找出全部受影響區塊?)
第一個區塊 包含 。假設目前索引 的 lowbit 是 ,令 。因 為奇數, 可被 整除,所以
因此 包含整個 ,當然也包含 。這證明了每個探訪區塊都確實需要更新。
還須證明沒有漏掉其他受影響區塊。任何包含 的區塊,其終點至少是 。對兩個相繼探訪的索引 、,考慮它們之間的 ,其中 。 的最低 位都是零,故 ,從而
所以 的起點嚴格大於 ,不能包含 。第一個終點 之前沒有候選;上述推理又排除了每段路徑間隙,包括下一個終點超過 時的最後間隙。因此每個受影響區塊恰好更新一次,單點加法後重新滿足儲存不變量,供之後每次查詢使用。
證明透視
查詢與更新的路徑回答不同問題
更新證明的關鍵一步,是當 為奇數時, 可被 整除。加上 lowbit 會向更高的位進位,所以下一個區塊嚴格更長,並包含上一個區塊。這種嵌套,正是被訪問的區塊恰好構成包含 的區塊鏈的原因。查詢證明用的是相反的結構:減去 lowbit 後,剩下的前綴恰好結束於被取走區塊的開始處,所以區塊互不相交,而不是互相嵌套。
單靠嵌套只能說明每個被訪問的區塊都受影響。要說明沒有漏掉,必須用另一個間隙論證:對 ,, 的 lowbit 等於 的 lowbit,所以 開始於 之後。界限 只用來停止迴圈,在兩個論證中都不起作用。兩個迴圈正負號相反,是這兩個不同不變量的結果,而不是要死記的公式。
例題 1.1.5
(更新一項,再核對區間查詢)
從八項原陣列執行 ADD(5, 2)。更新探訪 ,再到樹外的 。改變的項目是
其他 不變。現在 PREFIX(7) 得 ,所以
直接計算,改後的區間為 ,其和確實是 。更新位置 不應修改 ,因為 沒有包含該位置。查詢路徑 與更新路徑 雖有共同索引,卻不能互相代替。
例題 1.1.6
(大小不是二次冪的情況)
取 ,每個 ,所以 ,例如 ,,。執行 ADD(9, 3)。路徑是 :lowbit 為 令 變成 ,lowbit 為 令 變成 ,lowbit 為 令 變成 ,超過 ,迴圈停止。所以 ,,。(區間 )與 (區間 )不含位置 ,保持不變。之後 PREFIX(13) 經過 ,傳回 ,結果正確。
常見錯誤
(把 lowbit 當作區塊的起點)
對 ,lowbit 是 。若把 當作區塊起點,便得到 ,共九項,這是錯的。lowbit 是區塊的長度:,。
常見錯誤
(加上新值而不是變化量)
要在八項陣列上把 設為 ,調用 ADD(5, 2) 會令 、,因為原來 。所需的變化量是 ,這樣 。ADD 永遠是加上,不是設定。
在帶正負數的數據上追蹤不變量
上面的例題使用正數陣列。下圖另選兩個固定陣列,其中含負數;這是新例子,不是接續上一個更新。每次選擇操作,都由所選陣列重新開始。畫面的目標陣列表示增量操作要達到的結果,即使部分樹項仍待更新,目標仍會先列出。
儲存區間由索引決定,與數值的正負無關。非空區間的和可以為零;若它屬於查詢的分解,仍須讀取。同樣地,增加零也要訪問受影響項目,只是沒有數值改變。請分開觀察訪問進度與是否等於目標值。
先追蹤前綴查詢,再比較單點增量:減去 lowbit 會取走已完成的查詢區塊,加上 lowbit 則找下一個包含更新位置的區塊。兩條路徑證明的事情不同。空查詢 prefix(0) 合法;位置零的更新卻不合法。
為甚麼兩種操作都是對數時間?
命題 1.1.7
(兩種操作的對數成本)
設 。對 ,PREFIX(r) 至多迭代 次。對 ,ADD(p, delta) 至多訪問 個索引。樹儲存 個和。
證明
(清除位元與 lowbit 倍增)
查詢時減去 lowbit,會清除索引最低的一個非零位。因此迴圈次數等於原索引 的非零位數;當 ,最多是 。更新時,下一索引的 lowbit 至少是目前的兩倍,上面的證明已說明這一點。每個有效索引的 lowbit 不超過 ,所以探訪次數同樣最多為 。更新的索引本身未必加倍: 的下一站是 ,不是 ;至少加倍的是 lowbit。∎
樹儲存 個區間和,空間為 。從零樹開始,對每個 做
ADD(i, a_i),便可在 時間建立不變量。這是正確的簡單建構法,並非斷言不存在線性時間建構法。上述證明亦無須 為二次冪:若 ,PREFIX(13) 的路徑是 ,而位置 的更新仍經過 ,然後離開索引範圍。
增量、賦值,以及前綴相減背後的代數
ADD(p, delta) 是增加一個變化量,不是把 設成該參數。若要賦值為 ,應計算 ,執行加法;若另有保留原陣列,也要記錄 。沒有原陣列副本時,可用 RANGE_SUM(p, p) 在對數時間取得舊值。例如在原陣列把 設為 ,所需變化量是 ,不是增加 。結果 分別變成 。負數項及負增量都符合區間和的不變量。
反例模式
把和換成最小值,並不能沿用這些公式
陣列 與 在終點 、 的前綴最小值都同為 ,但它們在 上的最小值分別是 、。所以這兩個前綴最小值不能決定任意區間最小值;不存在像減去前綴和那樣,把較早部分的最小值「撤銷」的運算。
更新也不同。若儲存區間包含 ,其最小值為 ;把第一項增加至 後,新最小值是 。若只取舊儲存值 與新值 的較小者,便錯誤保留了 。受限制的最小值查詢變體須有自己的不變量及更新假設;本節無限制加法的證明並不適用。
練習與完整解答
每題均重新使用最初的八項陣列。
快速檢查
(PREFIX(6) 使用哪些項目?寫出其儲存區間。)
解答 · 答案
路徑是 ,選取 與 ,答案是 。
快速檢查
(執行 ADD(3, -4),哪些樹項目改變?新的 RANGE_SUM(3, 7) 是多少?)
解答 · 答案
更新路徑是 ,得到 。原來 的和為 ,新值為 。查詢也得到同一結果:
PREFIX(7) 為 ,PREFIX(2) 為 ,所以 。
快速檢查
(若以 調用更新迴圈,為甚麼不會前進?)
解答 · 答案
lowbit 的正索引定義不適用於零。即使程式位元運算在零得到零,下一個索引仍是零,造成無窮迴圈。外部從零開始的位置 ,須先轉成內部位置 。
快速檢查
(把 設為 ,求 PREFIX(7),並解釋更新參數為甚麼是負數。)
解答 · 答案
變化量是 ,所以 PREFIX(7) 變成 。若增加 ,原項會變成 ,處理的是另一個問題。
實作比較及其他變體可參閱 CP-Algorithms 的 Fenwick 樹文章。