儲存可以合併的摘要
假設陣列在兩次區間查詢之間會改變。對總和,我們可用逆運算把兩個前綴和相減;其他摘要未必有逆。比如知道前綴最小值,也不能求出每段最小值:[1,5,7] 與 [1,2,3] 的前綴最小值陣列相同,但索引 的最小值分別是 5、2。
線段樹使用另一種方法:儲存對齊區間的摘要,用少量互不相交區間合併回答查詢。單點賦值只改變包含該點的區間摘要。核心要求是合併運算有結合律,不要求交換律或減法。
使用陣列 ,,索引由零開始。全部區間左閉右開: 包含 ,且 ; 為空。單點賦值取代已有 ,不一定是在舊值上加一個量。
代數規格:結合運算與單位元
定義 1.3.1
(區間摘要的幺半群)
設摘要集合 有二元運算 ,要求結合律
並有單位元 ,滿足 。區間聚合是按從左至右次序取 乘積,空區間結果為 。這種結構稱為幺半群(monoid),不一定滿足 。
每個陣列元素提供一個摘要,可以是值本身,也可以是足以正確合併的較豐富物件。
| 區間問題 | 摘要與合併 | 單位元 |
|---|---|---|
| 總和 | 數值,加法 | |
| 最小值 | 擴充實數,取最小 | |
| 最大值 | 擴充實數,取最大 | |
| 有序串接 | 字串,左字串後接右字串 | 空字串 |
| 固定大小矩陣乘積 | 同一固定維度方陣,矩陣乘法 | 單位矩陣 |
| 平均值 | ,分別相加總和與數目 |
平均值要等查詢後才取 ,且要求 。若只把兩個平均值直接平均,當它們代表不同大小的群組時便錯。結合性取決於摘要表示,不只是所求統計量的名字。
數學總和例子使用精確運算。浮點加法並非精確結合,所以結果可依賴樹的括號分組。實作須訂明數值意義,儲存整數總和時也要使用足夠範圍。
補齊成完全二叉樹
設 是不少於 的最小二次冪。因 ,有 。樹使用陣列位置 ,位置 0 不用。對 ,輸入摘要放在葉 ;其餘葉放單位元。
每個內部位置 的左子是 ,右子是 ,而
左子永遠代表較前區間。每節點按此順序儲存其對齊葉區間的聚合。用單位元補齊不改變輸入聚合。
BUILD(a[0..n-1]):
m = smallest power of two with m >= n
T[1..2m-1] = identity summaries
for i = 0 to n-1:
T[m+i] = summary of a[i]
for v = m-1 down to 1:
T[v] = T[2*v] star T[2*v+1]
單點賦值重算祖先
ASSIGN(i, newValue): // 0 <= i < n
v = m + i
T[v] = summary of newValue
v = floor(v / 2)
while v >= 1:
T[v] = T[2*v] star T[2*v+1]
v = floor(v / 2)
命題 1.3.2
(補齊樹的不變量)
對補齊樹的每個節點 ,令 為 之下對齊葉區塊從左至右的聚合,補齊的葉取單位元。則 BUILD 之後 ,每次 ASSIGN 之後亦然。
證明
(由葉向上歸納,只有祖先會改變)
建樹。 由葉向上歸納即可證明區間摘要不變量:兩子代表相鄰區間,父合併取得串接後的聚合。結合律保證樹的分組等於所要的從左至右乘積。
賦值。 只有葉 的祖先包含被改元素,其他節點區間與它不相交,摘要仍正確。由下向上重算父,便在每個受影響層恢復不變量。因此賦值正確,不需逆運算,也不把 newValue 當作增量。∎
時根已是葉,沒有父要重算,同一程式仍有效。
為何迭代查詢需要兩個累積值
由葉索引區間 、 開始,保留左、右兩個累積值。左邊界取出的區塊,接在左累積值的尾端;右邊界取出的區塊,接在右累積值的前端。
QUERY(l, r): // 0 <= l <= r <= n
L = l + m
R = r + m
left = e
right = e
while L < R:
if L is odd:
left = left star T[L]
L = L + 1
if R is odd:
R = R - 1
right = T[R] star right
L = floor(L / 2)
R = floor(R / 2)
return left star right
根以下的層,奇數 是右子,其左兄弟不在剩餘查詢內,所以整個區塊必須現在取走。若 就是根,直接取走便完成整個剩餘區塊。若 是奇數,它是被排除的右邊界;最後包含的節點是 的左兄弟,索引為 ,也須先取走再上升。之後兩邊界都為偶數,剩餘相鄰對便可換成父節點。
概念視角組合
把區間看成二進區塊的並集
查詢在每一層、每個邊界最多取一個區塊,所以 是若干對齊區塊的不交並。依陣列次序閱讀,它們的大小先不遞減(來自左邊界,在上升時取得),後不遞增(來自右邊界)。例如 的大小是 ,即 b、cd、ef、g。兩個累加器恰好各自保存這個序列的前後兩半。
命題 1.3.3
(有序區間查詢)
假設補齊樹的不變量成立。對 ,QUERY(l, r) 傳回半開區間的從左至右聚合 ;當 時為 。每層至多取兩個區塊,所以使用 次合併。
證明
(兩個累積值的覆蓋與次序)
每輪開始時,原查詢聚合等於
中央區塊是目前層由 至 的節點,保持原次序。起初它們恰好是所求葉,兩個累積值都是單位元。
取奇數左邊界,就是移除第一個中央區塊,接到 left 尾端。取奇數右邊界,就是移除最後一個中央區塊,接到 right 前端,沒有跳過、重複或重排任何葉。邊界為偶數後,由已儲存節點不變量,把兩子換成父仍保留有序中央聚合;結合律容許此重新分組。
中央沒有區塊時,left star right 就是原區間聚合。空查詢不進迴圈,傳回 。證明從未交換兩個區塊,故不需交換律。
迴圈會終止: 輪後 而 ,所以到 時 不再成立。每輪至多取兩個區塊,由此得到所述成本。∎
證明透視
兩個累積值的證明在哪裏用到各項假設
不顯而易見的一步,是保留兩個累積值:左區塊接到 left 尾端,右區塊接到 right 前端。迴圈由兩端向內推進,所以在下面的追蹤中,區塊依 的次序出現,而不是陣列次序。把右區塊放在前端的理由來自不變量而不是程式碼:不變量準確說明了剩餘中央區塊位於兩個累積值之間。
結合律只在兩個子節點換成父節點,以及最後重新分組乘積時使用。單位元用於空的累積值和補齊的葉。交換律完全沒有用到。奇偶測試才是證明的實質內容:測試之後 和 都是偶數,所以中央節點構成完整的兄弟對。若省略對 的測試,節點 會被漏掉;若取 而不是 ,會加進被排除的葉。半開區間的約定使 成為不包含的邊界,條件 才恰好準確。
次序真正重要的追蹤
例題 1.3.4
(串接索引 1 至 6)
取八個單字元元素 [a,b,c,d,e,f,g,h],所以 。相關節點有 、、、。查詢 。
| 輪次 | 進入時 | 取左區塊 | 取右區塊 | 之後 left | 之後 right |
|---|---|---|---|---|---|
| 1 | b | g | |||
| 2 | bcd | efg |
下一對邊界為 ,結果是 bcd 後接 efg,即 bcdefg。實際遇到區塊的次序是 b,g,cd,ef,不是最後陣列次序;雙累積值恢復了正確順序。
若右更新錯寫成 right star T[R],第二輪會得到 gef,最後答案成為 bcdgef。總和或最小值會掩蓋此錯誤,因兩者有交換律;有序串接則把錯誤顯示出來。
例題 1.3.5
(補齊樹上的最小值)
設 ,,使用最小值摘要,所以 。葉 為 , 為 。於是 ,,。查詢 由 開始。第 1 輪: 為偶數, 為奇數,所以 ,;邊界變成 。第 2 輪:兩者皆偶,得 。第 3 輪: 為奇數,所以 ,;邊界變成 。答案為 ,正確。補齊的葉從未被讀取。
例題 1.3.6
(單一元素與空區間)
設 ,使用求和,,所以 ,。查詢 的 。此時 為奇數,所以 ,; 為偶數。兩者減半成 ,答案為 。查詢 的 ,迴圈不會執行,答案是 。對 ASSIGN(0, 9), 設為 ,下一個 令迴圈立即結束,因為沒有父節點要重算。
常見錯誤
(取 T[R] 而不是 T[R-1])
為奇數時,節點 本身剛好在區間之外;最後包含的節點是 ,程式碼會先把 減一。在八個字母的追蹤中,第一個右邊界是 ,而 是索引 ,在 之外。取它會把區間不包含的字元加進答案。
常見錯誤
(把區間當作閉區間)
查詢 不含 。要串接索引 至 ,必須調用 QUERY(1, 7)。對八個字母調用 QUERY(1, 6) 會得到 bcdef,無聲地漏掉 g。若實作也接受閉區間,邊界處需要轉換成 。
固定大小的非交換摘要也可用仿射映射。把 表示為 ,定義合併為先施左映射,再施右映射:
複合有結合律,單位元為 。次序重要:先 再 ,得到 ;反過來則為 。只要儲存合併及所求左至右聚合採同一定義,查詢程式就適用此約定,也適用矩陣乘積約定。
使用列向量時,先施矩陣 再施 對應乘積 ,不可把這個作用約定與明確要求 的陣列查詢混淆。
下圖追蹤已解練習所用的八字母查詢,並演示其中的仿射複合方法。若想獨立作答,請先嘗試這兩題。
說清複雜度在計算甚麼
樹有 個摘要位置,建立需 次合併,賦值重算 個祖先。查詢每層至多取兩個區塊,所以需 次合併及迴圈步驟。 或空區間仍有常數工作。
摘要大小固定、每次合併為常數時間時,才得到 建立時間與空間,以及 更新/查詢時間。在所訂運算假設下,固定大小總和、最小值及矩陣符合此模型。真正建立長串接字串則不同:合併要複製字元,回傳 個字元至少需 。字串追蹤證明的是有序正確性,不保證對數時間產生子字串,也不保證全樹儲存的總字元數只有線性。
若每葉是一個字元,而且 為二次冪,單是每層就儲存 個字元,全樹實際字元數已達 。
改變更新種類需要額外代數
反例模式
只有平均值並不是結合摘要
若合併定義為 ,對三個輸入 ,先合首兩個再合第三個得到 3;先合末兩個則得到 ,真正平均卻是 2。這運算沒有結合律,也不能正確合併不同大小群組。
應把每個輸入表示為 ,分別相加兩座標,以 為單位元。查詢帶回總和及正確數目,非空區間可在最後正確取平均。空區間雖有明確摘要 ,平均值仍未定義。
上述算法實作單點賦值,不會因為任意改一個快取節點,就自動實作區間更新。區間加 時,總和摘要需要實際輸入數目 : 變成 。相同加法正確分配至相鄰摘要的合併,而兩次加法標記以相加方式複合。
更新、摘要合併及更新標記複合之間的相容性,正是懶惰傳播實作必須證明的條件。若 表示標記 對摘要的作用,統一幺半群作用設計的一組清楚充分條件是
此設計的單位標記作用為恆等映射。其他懶惰設計可把作用限於非空區間,或另外攜帶長度數據,並各自證明相容性。存在待處理標記時,部分覆蓋的查詢或更新使用子摘要之前,還須下推標記或作其他理解標記的求值;上述普通查詢程式沒有做這項處理。標記複合未必可交換,只有查詢運算具結合律,不會自動提供這些額外更新規則。
有解練習
快速檢查
(1. 從合法摘要取平均)
三個輸入是 ,求每葉的總和/數目摘要、合併摘要及平均。比較兩種反覆未加權平均。空區間平均查詢在數學上應報告甚麼?
解答 · 解答 1
葉為 ,合併為 ,平均為 5。兩種反覆平均是 及 ,兩者都錯。空區間摘要是 ,但平均未定義,不能回報平均零。
快速檢查
(2. 解釋右累積值的合併方向)
八字母追蹤第一輪後,right 是 g,下一個右區塊是 ef。為何必須得到 efg 而非 gef?只測整數總和能否發現這個特定錯誤?
解答 · 解答 2
新取區塊涵蓋索引 4、5,比 right 已有的索引 6 更前,必須放前端。整數加法有交換律,次序錯仍得相同總和,不能揭露此錯誤。即使特定運算令次序影響看不見,正確性證明仍要求次序。
快速檢查
(3. 賦值改變查詢,端點卻不變)
對 [8,3,6,2,7,4,5,9] 使用最小值摘要,先求 。再把索引 3 賦值為 10,重新求該區間。之後全陣列最小值是多少?
解答 · 解答 3
起初查詢元素是 ,最小值 2。賦值後變成 ,最小值 4。全陣列最小值仍是 3,在查詢以外的索引 1。重算被改葉的祖先可恢復兩個答案;每個區間都直接回傳根,會得到錯的查詢值。
快速檢查
(4. 按已訂次序聚合仿射映射)
使用 ,按陣列次序合併 、、。求結果映射及在 2 的值。為何樹可改括號,卻不能改次序?
解答 · 解答 4
先有 ,再得 ,在 2 的值為 。複合的結合律容許兩種括號分組,但不具交換律,重排映射會變成另一個查詢。單位映射 使補齊及空有序乘積一致。