Li Chao 樹（Li Chao tree）

凸包優化快卻挑剔：其最簡形式要求線按斜率排序插入、查詢按 x 排序到來。真實問題不總是這麼配合。Li Chao 樹是做同一件事的更有彈性的結構——維護一組直線並回答「在這個 x 處哪條線最低（或最高）？」——它允許線以「任意」順序插入、在「任意」x 處查詢，各為 O(log 座標範圍)，代價只是最好情況下稍慢一點。

它是一棵建在所有可能查詢 x 值範圍上的線段樹。每個樹節點涵蓋一個 x 區間，存一條直線：在迄今所見的線中，於該節點中點處最佳（比方說最小）的那條。要插入一條新線，你在區間中點處把它與該節點存的線比較；在那裡較好的留作節點的線，把落敗者下推到它仍可能勝出的那半個區間——它與留下的線在端點處的相對大小，告訴你要遞迴進哪個子節點。因為兩條直線至多相交一次，落敗者至多能在兩半中的一半勝過勝出者，所以你永遠只遞迴進一個子節點，使每次插入為 O(log 範圍)。要查詢點 x 處的最小值，你沿 x 從根走到葉，並取沿途經過的每條存線的最小值，同樣是 O(log 範圍)。

所以 Li Chao 樹給出 O(log C) 的插入與查詢，C 為座標範圍大小，且對斜率或查詢不做任何排序假設——正是當樸素凸包優化的單調性前置條件失效時你會伸手去拿的東西。要誠實面對的取捨：它需要查詢座標落在一個已知、有界的範圍內（你在該範圍上建樹，或先做座標壓縮），它回答的是點查詢而非輕易支援刪除，且它的常數因子與 log 範圍深度使它比起凸包假設成立時那個攤還 O(1) 的凸包略重一些。標準的擴充是存線段（每條只在某子範圍上有效）而非完整直線，代價是多一個 log 因子。