數值會改變時,問題有甚麼不同?
設 是整數陣列,。我們要交錯執行兩種操作:把某個 增加整數 ,以及查詢連續區間 的和。逐項重算區間最多要做 次加法。前綴和陣列可加速查詢,因為
但改變 就會改變 。普通前綴和陣列因此以可能需要線性時間的更新,換取常數時間查詢。 二元索引樹,亦稱 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) 合法;位置零的更新卻不合法。
二元索引樹:每一項究竟儲存哪個區間?
二元索引樹不會逐一儲存所有前綴和;每一項只儲存一個特定區間的總和。先追蹤前綴查詢,再比較單點增量需要更新哪些項目。
prefix(0) 是空和。單點增量只使用位置 1 至 8;位置 0 不是可更新的位置。
目前操作: prefix(7)
| 索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 操作前的陣列 | 3 | -2 | 5 | 1 | -4 | 6 | 0 | 2 |
八個項目所儲存的區間
每條橫線覆蓋其列所儲存的完整陣列區間;粗框表示剛訪問的項目;虛線框表示更新仍待訪問。下表列出所有區間及數值。
| 項目 | 二進制索引 | lowbit | 儲存區間 | 目前快取和 | 演算法進度 |
|---|---|---|---|---|---|
| T[1] | 0001 | 1 | [1, 1] | 3 | 未讀取 |
| T[2] | 0010 | 2 | [1, 2] | 1 | 未讀取 |
| T[3] | 0011 | 1 | [3, 3] | 5 | 未讀取 |
| T[4] | 0100 | 4 | [1, 4] | 7 | 未讀取 |
| T[5] | 0101 | 1 | [5, 5] | -4 | 未讀取 |
| T[6] | 0110 | 2 | [5, 6] | 2 | 未讀取 |
| T[7] | 0111 | 1 | [7, 7] | 0 | 未讀取 |
| T[8] | 1000 | 8 | [1, 8] | 11 | 未讀取 |
- 下一個迴圈索引 i
- 7
- 上次訪問的項目
- 無
- 已訪問索引
- 空
- 已累積總和
- 0
- 已讀取的快取區間數
- 0
- 已取出的不相交區間
- 空
- 查詢不變量
- 0 + (9) = 9
步驟 1 / 5
累積和為 0,尚未讀取任何快取區間;迴圈變數 i 從 r 開始。
為何這些跳躍正確
對正索引 j,lowbit(j) 是整除 j 的最大二次冪。T[j] 儲存 a[j−lowbit(j)+1] 至 a[j] 的總和,兩端均包括在內。二進制顯示幫助辨認最低為 1 的位元;在此 1 至 8 的索引中,可用 j & −j 計算。第 0 項沒有儲存區間,也永不更新。
計算 prefix(r) 時,未處理部分是 [1,i]。讀取 T[i] 恰好取出其後綴 [i−lowbit(i)+1,i],留下 [1,i−lowbit(i)]。故「累積和+剩餘前綴和」始終等於 prefix(r)。每個完整步驟同時加入區間和並推進 i。取出的區間互不重疊,聯集正是 [1,r]。每次跳躍清除一個設為 1 的位元;此處最多讀三個區間。
執行 add(k,δ) 時,若 T[j] 的區間包含 k,規定增量為 δ;否則為 0。設目前受影響項目為 j,L=lowbit(j)。若中間終點 t=j+s 且 0<s<L,則 lowbit(t)≤s,其區間起點因此在 j 之後,不可能包含 k≤j。下一終點 j+L 的 lowbit 至少為 2L,故其區間包含目前區間,亦包含 k。從 j=k 開始,這些跳躍會依次訪問不超過 8 的所有且僅有受影響項目。此處最多訪問四項。
把 δ 加到每個包含 k 的區間,便恢復目標陣列的不變量。更新尚未完成時,部分快取和仍可表示舊陣列。表格因此分開顯示訪問進度與是否符合目標:δ=0 時,一項可以符合目標,但仍待訪問。本模型不會在更新途中插入前綴查詢。
只計演算法讀取的快取區間及執行的快取加法。建立預設樹、顯示區間及核對目標總和,均屬計數之外的唯讀教學操作。總和為零的區間可以非空;負數亦適用於這些總和操作,前綴和不必單調。
閱讀完整追蹤
- 累積和為 0,尚未讀取任何快取區間;迴圈變數 i 從 r 開始。
- [7, 7]: 0 + (0) = 0; i = 7 − 1 = 6. 讀取此區間,把其總和加入累積和,再從迴圈索引減去 lowbit。畫面上的 i 是完整執行本次迴圈後的索引。
- [5, 6]: 0 + (2) = 2; i = 6 − 2 = 4. 讀取此區間,把其總和加入累積和,再從迴圈索引減去 lowbit。畫面上的 i 是完整執行本次迴圈後的索引。
- [1, 4]: 2 + (7) = 9; i = 4 − 4 = 0. 讀取此區間,把其總和加入累積和,再從迴圈索引減去 lowbit。畫面上的 i 是完整執行本次迴圈後的索引。
- 迴圈索引已為 0。不相交區間恰好覆蓋所求前綴,因此累積和就是其總和。 prefix(7) = 9.
每次追蹤均由所選預設陣列開始。改變控制項會重新執行該次操作;更新後的樹不會帶入另一次追蹤。本圖不會向外儲存或請求資料。
為甚麼兩種操作都是對數時間?
命題 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 樹文章。