針對競賽程式設計的線段樹詳解

如果你曾因為一道需要對陣列反覆更新並查詢區間數千次的題目而逾時，那麼線段樹正是把這堵牆變成簡潔、對數級解法的資料結構。

線段樹是競賽程式設計中最重要的工具之一。它能回答關於陣列某段連續區間的問題，例如求和、最小值、最大值或最大公因數，同時還能修改陣列，每次操作都只需 O(log n) 的時間。當一道題混合了大量更新與大量查詢時，正是這種效率把能通過的解法與會逾時的解法區分開來。

樸素陣列為何力不從心

設想一個有一百萬個數字的陣列。用迴圈回答單次「從索引 L 到 R 求和」的問題是 O(n)，而單次單點更新是 O(1)。這聽起來還不錯，直到題目拋出幾十萬次混合的更新與查詢。總工作量會膨脹到每次查詢大約 O(n)，這就太慢了。

前綴和陣列可以解決區間求和查詢，但一旦數值發生改變就會失效，因為每次更新都迫使你重建前綴和。線段樹則一次性解決了問題的兩個方面：快速查詢與快速更新，即便它們交錯出現也不在話下。

線段樹的運作原理

線段樹是一棵基於分治思想建構的二元樹。根節點代表整個陣列。每個內部節點代表一段區間，並把該區間一分為二，分別儲存在它的兩個子節點中。葉子節點代表單個元素。

每個節點儲存其區間的某種聚合值，例如和或最小值。由於這棵樹大約有 2n 個節點，高度約為 log n，兩項核心操作便變得開銷很小：

• 區間查詢：從根節點向下走訪，合併那些完全落在查詢區間內的節點的預先計算值，只對部分重疊的節點進行遞迴。最多觸及 O(log n) 個節點。
• 單點更新：改變一個葉子節點，然後向上移動並重新計算受影響的祖先節點。只有從葉子到根的一條路徑會變化，因此是 O(log n)。

「合併」這一步正是結構變得靈活的地方。把加法換成 min、max 或 gcd，同樣的骨架就能回答一個完全不同的問題。練就這種思維上的靈活替換，正是我們在 BIAA 競賽程式設計方向中反覆訓練的技能之一。

用於區間更新的懶惰標記下推

對於許多難題，單點更新還不夠。有些題目要求你給某個區間內的每一個元素加上一個值，或者把一個值賦給整段區間。逐個更新每個葉子又會回到 O(n)。

解決辦法是懶惰標記下推。你不必立刻把更新一路推到底，而是把一個待處理的改動（稱為懶惰標記）儲存在完全覆蓋更新區間的最高層節點上。這項工作被延後，直到後續某次查詢或更新確實需要穿過該節點時，你才把標記「下推」到它的子節點。

初學者最容易忘記的一條規則：在遞迴進入某個節點的子節點之前，務必先下推待處理的標記。一旦遺漏，更新就會悄無聲息地遺失，產生幾乎正確卻幾乎無法除錯的答案。

有了懶惰標記下推，區間更新和區間查詢都能以 O(log n) 執行。這一模式在較難的 USACO Gold 和 Platinum 題目以及整個 Codeforces 中不斷出現，因此非常值得精通。

一份練習路線圖

1. 建構一棵支援單點更新和區間求和查詢的求和線段樹。
2. 把它改寫為支援區間最小值和區間最大值查詢，以吃透合併這一步。
3. 加入懶惰標記下推以支援區間加法，再支援區間賦值。
4. 在基礎操作變得駕輕就熟之後，再攻克二維區間查詢和 segment-tree-beats 等變體。

線段樹更看重深思熟慮、有條理的練習，而非單純的天賦。備戰 USACO 比賽的學生會在通往 Gold 和 Platinum 的路上很早就遇到這一結構，而一份胸有成竹的實作能在賽場上省下寶貴的幾分鐘。

如果你想要有指導的練習、程式碼審查，以及從陣列到進階資料結構的清晰進階路徑，歡迎了解 BIAA 競賽程式設計專案，開始打造頂尖選手所依賴的工具箱。