前綴最小值為何不能相減
設 為實數,。我們需要兩個操作:把 換成指定值,以及對 求 。前面的 Fenwick 樹一課解釋了為何兩個前綴最小值無法決定任意區間最小值。這個限制不妨礙其他數據結構解決此問題。
線段樹儲存一族嵌套區間的數據。這裏使用單點賦值而非增量。線段樹與 Fenwick 樹是不同結構;它透過儲存的不變量直接處理區間最小值及賦值。
建樹與不變量
定義 1.2.1
(最小值線段樹)
設 為實數,。最小值線段樹是以 為根的二叉樹。當 ,區間 的節點有兩個子節點 和 ,其中 。葉節點 儲存 ,每個內部節點儲存兩個子節點所儲存值的最小值。節點 所儲存的值記作 。
對樹由葉向上作歸納,所儲存的值滿足不變量
子區間把父區間分割,不遺漏任何元素,也不包含區間外元素。重複分割後恰有 個葉節點。每個內部節點有兩個子節點,所以樹共有 個節點,能在 時間和空間自底向上建成。
要賦值 ,沿唯一包含 的子節點下降,把葉節點值換成 ,再沿路返回並重新計算最小值。路徑外葉節點不變;路徑上每次由已正確的子節點重新計算,恢復不變量。因此更新後根及其他所有節點都正確。無論 比舊值大或小,方法均適用。
查詢與成本
查詢 時從根遞歸訪問。對節點區間 :
- 若 與 不相交,返回 ;
- 若 ,返回它儲存的最小值;
- 否則返回兩個子節點結果的最小值。
符號 是最小值運算的概念性單位元,並非陣列元素:。公開查詢要求非空有效區間,故最終答案有限。實作也可用明確的空結果標記表示不相交。
命題 1.2.2
(最小值線段樹的正確性與成本)
設 上的最小值線段樹滿足不變量,並假設數值比較、索引與每個數值的儲存皆為常數成本。
- 按上述方式作單點賦值 後,每個節點的不變量再次成立。
- 對 ,查詢返回 。
- 樹高至多 ;查詢每一層至多訪問四個節點,賦值每一層訪問一個節點。因此兩種操作都耗時 ,包括 。
證明
(沿路重算、區間覆蓋與四節點界)
賦值。 區間不含 的節點只依賴 以外的葉節點,所以其儲存值不變而且仍然正確。區間含 的節點構成由葉節點 到根的路徑。葉節點現在儲存 。由下而上,路徑上每個節點都重新取兩個子節點的最小值:其中一個子節點在路徑上,已經正確;另一個不在路徑上,沒有改變且正確。兩個子區間分割父區間,所以兩個儲存值的最小值就是父區間上的最小值。因此每個節點的不變量都成立。
查詢。 對被訪問的節點 ,以 表示它返回的值,並約定 。對 的高度作歸納,證明 。若 與 不相交,集合為空,。若 ,由不變量得 。否則 與 相交但不被包含,所以 至少有兩個元素,是內部節點。它的兩個子區間 分割 ,因此 是 與 的不相交並集,兩個子結果的最小值就是並集上的最小值。在根處 非空,所以答案有限。
成本。 在深度 ,每個區間至多有 個元素,所以樹高至多 。稱與 相交但不被包含的節點為部分相交節點。若一個區間既含 內的索引又含其外的索引,它必含兩個相鄰索引,其中恰有一個在 內;所以部分相交節點必同時含 和 ,或同時含 和 。同一深度的節點區間互不相交,所以每層至多一個節點含 、至多一個節點含 ,即每層至多兩個部分相交節點。查詢只在部分相交節點之下遞歸,因此每層至多訪問四個節點,合共至多 個。賦值沿一條根至葉路徑進行。每次訪問成本為常數。∎
證明透視
查詢歸納法對最小值運算的要求
不顯而易見的一步,是對每個被訪問的節點都證明同一個命題,而不只是完全覆蓋的節點。約定 後,不相交、被覆蓋和需要分拆三種情況共用一個命題,一次歸納就能處理。
分拆的情況只用到兩件事:子區間分割 ,以及並集的最小值等於兩個最小值的最小值。證明從未用到冪等性,所以同一證明適用於任何有單位元的結合運算,例如以 為單位元的求和。不相交的情況正是需要單位元的原因:它必須對每個 都滿足 。
成本論證用到樹的另一個性質:同一深度的區間互不相交。正是這一點,把「部分相交節點含有跨過 或 的相鄰索引對」變成「每層至多兩個部分相交節點」。若子區間可以重疊,每層至多訪問四個節點的界就不再成立。
常見的失敗有兩種:對不相交節點返回錯誤的值,以及用比賦值更弱的更新規則。下面兩個區塊各給一個具體例子。
反例模式
零不是不相交節點的安全返回值
斷言:不相交節點可以返回 ,因為看似中性的數不會影響答案。取 。根 有子節點 和 。查詢 :根是部分相交節點,子節點 被覆蓋並返回 ,子節點 不相交,按此斷言返回 。根於是返回 ,而真正答案是 。對任何有限值 ,只要陣列各元素都大於 ,同樣失敗,因為此時 。不相交的返回值必須對每個 都滿足 ,這迫使 ,或使用明確的空結果標記。
常見錯誤
(把賦值當作減小)
很容易想到把路徑上每個節點更新為 。當 不大於舊葉節點值時這是對的,但值增大時就錯。在 上賦值 :此規則在葉節點及其上方都保留 ,因此查詢 仍返回 ;可是陣列現在是 ,答案應為 。值增大可能移走原來的最小值,所以每個祖先都必須由兩個子節點重新計算。
更新例子
例題 1.2.3
(五個數的查詢與賦值)
從 開始。根 分成 和 。查詢 時合併 、 和 的值,得 。現在賦值 。重新計算 得 ,根得 。同一查詢現在返回 。單點賦值不是把 加到舊值上。
例題 1.2.4
(一次查詢訪問的節點)
在 上,節點依次為 ,然後 和 ,然後 、、、,再然後 和 。查詢 訪問全部九個節點。根、、 和 是部分相交節點。葉節點 、、 被覆蓋,分別返回 、、;葉節點 和 不相交,返回 。所以 返回 , 返回 , 返回 ,根返回 。各層訪問的節點數為 ,沒有超過四個。
例題 1.2.5
(只有一個葉節點的樹)
設 ,。根 同時是唯一的葉節點,沒有子節點,也沒有祖先。查詢 時根被完全覆蓋,返回 。賦值 只是替換儲存值;沒有路徑需要重算,所以下一次查詢返回 。兩個操作都是常數時間,與 一致。
習題與解答
快速檢查
(減小值。從 出發,賦值 。 的最小值及根的最小值是多少?)
解答 · 答案
兩者都是 。陣列變成 ;只需重新計算葉節點 的祖先,即 和根。
快速檢查
(完全覆蓋查詢。為何建樹後查詢 只需常數時間?)
解答 · 答案
根被完全覆蓋且已存有所求答案,不需訪問子節點。
快速檢查
(單點查詢。在 上,查詢 訪問哪些節點?返回甚麼?)
解答 · 答案
訪問 、、、 和 。節點 和 不相交,返回 ;葉節點 被覆蓋,返回 ,所以答案是 。
快速檢查
(節點計數。 時,樹有多少個葉節點、多少個節點?)
解答 · 答案
有 個葉節點和 個內部節點,因為每個內部節點有兩個子節點,而樹有 個葉節點。總數為 。