程式設計面試：如何用 Li Chao Tree 支援動態直線區間最小值？
題干與適用場景
系統線上接收直線 y = m x + b，支援任意順序插入；查詢給定整數 x 上所有直線的最小值。查詢點不單調，斜率也不單調。延伸問題可能要求直線只在區間 [l, r] 有效，或將查詢改為最大值。
這題適合考察動態規劃最佳化、分治不變量與線段樹實作。高品質回答要先說明值域是否離散且有界，再解釋每個節點只保留一條「在某個位置勝出」的候選直線，並證明被淘汰直線不會在該節點區間重新勝出。
面試官考察點
- 能否從每次掃描所有直線的
O(n)查詢推導瓶頸。 - 是否理解中點比較、交換與遞迴方向構成的 Li Chao 不變量。
- 能否處理任意斜率、重複直線、負座標與極值溢位。
- 是否區分離散整數值域、連續域與區間直線三種實作邊界。
- 是否給出
O(log C)單次插入/查詢與O(log^2 C)線段插入複雜度。 - 能否說明斜率與查詢點單調時，普通 Convex Hull Trick 可能更簡單。
回答前需要釐清的問題
- 查詢
x是整數還是實數？值域是固定[L, R]還是動態擴展？這決定遞迴深度與是否需要座標壓縮。 - 要最小值還是最大值？是否允許空集合？空集合的哨兵值不能與真實答案衝突。
- 斜率、截距與答案的最大絕對值是多少？需要多寬的整數或飽和乘法？
- 直線是否只在
[l, r]生效？區間插入會把直線分發到多個樹節點。 - 斜率插入或查詢是否單調？若單調，單調佇列式 CHT 可能比 Li Chao 更省常數。
30 秒回答框架
我先把整數查詢域 [L,R] 建成線段樹，每個節點保存一條目前候選直線。插入新線時比較左右端點與中點；若新線在中點更優，就和節點線交換。交換後，舊線只可能在左半或右半繼續勝出，因此依端點比較把它遞迴到一側。查詢沿根到葉路徑取所有節點直線值的最小值。值域長度為 C 時插入與查詢都是 O(log C)，區間直線插入為 O(log^2 C)；最大值只要反轉比較方向。
分步驟深入解答
1. 樸素方案與瓶頸
維護直線清單，每次查詢計算所有 m x + b 的最小值，時間是 O(numberoflines)。若這是動態規劃轉移，插入與查詢交錯且順序任意，不能依賴斜率或查詢點排序，因此要把比較工作分攤到值域區間。
2. 節點不變量
節點代表閉區間 [lo, hi]，保存直線 cur。不變量是：在該區間內，所有尚未遞迴到子節點的直線中，cur 至少在一個候選位置不劣；其他直線若仍可能成為最優，只會被送到左或右子區間。葉節點只需保存單點最優直線。
3. 中點交換與遞迴方向
設新線為 nw、節點線為 cur、中點為 mid。若新線在 mid 的值小於節點線，交換兩線，讓節點保留中點較優者。交換後比較 nw(lo) 與 cur(lo)：若舊線在左端較優，它可能在左側重新勝出，遞迴左子；否則比較右端並遞迴右子。兩條直線差是一次函數，最多一次交點，所以只需遞迴一側。
add(node, lo, hi, nw):
mid = (lo + hi) // 2
left = nw(lo) < cur(lo)
middle = nw(mid) < cur(mid)
if middle: swap(nw, cur)
if lo == hi: return
if left != middle: add(leftChild, lo, mid, nw)
else: add(rightChild, mid + 1, hi, nw)實作要使用安全中點公式，並在 m * x + b 可能超過 64 位時使用更寬整數、檢查或飽和策略。
4. 查詢路徑
查詢單點 x 時，從根遞迴到包含 x 的葉子，同時計算每個節點保存直線在 x 的值並取最小值。其他區間不包含該點，不需要訪問。動態節點只為實際插入經過的區間分配記憶體；空節點回傳正無限哨兵。
5. 區間直線插入
若直線只在 [ql, qr] 生效，可用普通線段樹區間分解，完整覆蓋的節點直接執行一次 Li Chao 插入，部分覆蓋則繼續遞迴。區間分解訪問 O(log C) 個節點，每個節點插入 O(log C)，總複雜度 O(log^2 C)，查詢仍是 O(log C)。
6. 離散座標與連續查詢
若只查詢已知離散 x 集合，先排序去重並用索引作為葉子域，避免為巨大空值域建樹。若查詢是實數，必須給出精度與終止條件；整數 Li Chao 的遞迴證明不能直接套用無限連續域，通常要限定區間並設定浮點比較誤差。
7. 與 Convex Hull Trick 的取捨與測試
斜率單調、查詢點也單調時，deque 維護的 CHT 常數較小；斜率任意、查詢任意時 Li Chao 更穩健，但節點與遞迴常數較大。測試要覆蓋空集合、單點域、重複斜率、相同直線、負座標、中點交點、只覆蓋一端點的直線、極大乘積與最大值查詢，並和逐條列舉結果比較。
高品質示範回答
我會先確認查詢域是固定整數區間，還是需要座標壓縮。對 [L,R] 建 Li Chao Tree，每個節點存一條目前候選線。插入時比較端點與中點；中點較優的線留在節點，另一條依兩條直線相對順序只遞迴到左或右子區間。因為兩條直線的差是一次函數，舊線不可能在兩個不相鄰方向重新勝出。單點查詢沿一條根葉路徑取最小值，插入與查詢都是 O(log C)。若斜率與查詢都單調，我會改用 CHT；若線段有生效區間，先做線段樹分解，複雜度變成 O(log^2 C)。
常見錯誤
- 只比較中點不遞迴 → 另一條線可能在端點勝出 → 結合端點與中點決定唯一遞迴方向。
- 假設斜率必須單調 → 任意順序時結果錯誤 → 使用 Li Chao 區間不變量，或明確改用適用的 CHT 前提。
m * x + b的 64 位乘法無檢查 → 極值溢位改變比較順序 → 使用更寬型別或明確溢位策略。- 動態域無限擴展 → 遞迴沒有終點 → 先限定整數域、離散化座標或設定浮點精度。
- 區間插入複製到每個葉子 → 複雜度退化 → 用線段樹區間分解後在完整覆蓋節點插入。
- 空節點回傳零 → 最小值被錯誤壓低 → 使用和答案範圍隔離的正無限哨兵。
追問及應對
如果要求最大值怎麼辦？
把比較方向全部反轉，或將每條直線的 m 與 b 同時取反後求最小值再取相反數。空集合與溢位語義也要一起保持，不能只改最後回傳值。
值域達到 10 的 18 次方，仍能開陣列樹嗎？
不能預先配置所有節點。使用隱式動態樹，只在插入訪問的路徑上建立節點；遞迴深度約為值域位數。若實際查詢座標有限，座標壓縮通常更省記憶體。
兩條直線在中點相等，如何避免錯誤分支？
固定平手規則，例如優先保留舊線或依斜率排序。分支判斷使用嚴格不等式，端點比較也保持同一規則，確保相同直線不會無限遞迴。
如何證明只遞迴一邊？
兩條直線之差仍是一次函數，最多只有一個交點。交換後若舊線在中點較差，它若能在區間內勝出，只能位於一個端點方向；端點與中點的符號變化唯一決定左或右。
什麼時候 CHT 更合適？
當直線斜率按單調順序加入、查詢點也單調時，凸包佇列可攤銷 O(1) 查詢或 O(log n) 查詢，程式與記憶體更小。斜率或查詢亂序、需要區間直線時，Li Chao 的通用性更有價值。