凸包優化（convex hull trick）

有些動態規劃轉移長成 dp[i] = 在 j < i 上取（某條直線在 x_i 處的值）的最小值：每個較早的狀態 j 貢獻一條直線 m_j * x + b_j，而要算 dp[i]，你問「在所有這些直線中，哪一條在查詢點 x = x_i 處給出最小值？」對每個 i 都把每條線都算一遍是 O(n^2)。凸包優化加速此事，靠的是注意到：在任何查詢點，一組直線的最小值由這些線的下包絡給出——一個分段線性的凸形——而大多數線根本無關緊要，因為它們處處都在包絡之上。

把每個候選想成圖上的一條直線。下包絡就是你從下方往上看會見到的邊界：對每個 x，最低的那條線。處處都不是最低的線可以整條丟掉。這個技巧只維護組成此包絡的那些線（它是這些線的下凸包，名稱由此而來），按斜率排序。要找查詢 x 處的最小值，你在包絡上二分搜尋涵蓋 x 的那一段，O(log n)。當查詢點按排序順序到來、且線按斜率排序加入時——這在動態規劃中很常見——你可用單調堆疊與移動指標使加入與查詢攤還 O(1)，得到 O(n) 或 O(n log n) 的動態規劃。加入一條新線時，會從凸包彈出被它變得多餘的線，正如用葛立恆掃描建凸包一樣。

對「直線最小值」形式的轉移，這把 O(n^2) 的動態規劃變成 O(n log n)（已排序、配二分搜尋）或 O(n)（完全單調）——是成本可分解為「斜率乘以 x 加上偏移」這類問題（如某些分割與排程動態規劃）的標準加速法。誠實的限制：基本版本要求線按單調斜率順序插入，且（為了 O(1) 查詢）x 查詢也要單調；違反任一個，你就得排序、改用平衡結構、或換成 Li Chao 樹，後者能以各 O(log 範圍) 處理任意的插入與查詢順序。此外，你必須分清你是在取最小（下包絡）還是取最大（上包絡）——它們互為鏡像，搞混是經典的臭蟲。