題目與使用場景
區間樹適合動態時間段、預約與資源占用查詢。關鍵是用左端點排序的平衡樹保存區間，並在每個子樹維護最大右端點，跳過不可能相交的分支。
面試官考察什麼
- 是否準確處理閉區間邊界與相交條件。
- 是否說明
maxEnd的定義與維護範圍。 - 是否利用增強欄位剪枝，而不是遍歷全部節點。
- 是否在旋轉、插入與刪除後更新增強欄位。
- 是否處理重複區間、空樹與刪除不存在元素。
- 是否給出對輸出敏感的時間複雜度。
作答前的釐清問題
- 區間是閉區間、開區間還是半開區間？
- 端點型別是整數、浮點還是時間戳？
- 是否允許重複區間，刪除按 ID 還是端點匹配？
- 查詢要全部結果還是只要一個相交區間？
- 是否要求線上插入刪除與自動平衡？
- 結果順序是否必須按左端點排序？
30 秒回答框架
「我以區間左端點作為樹鍵，每個節點保存右端點與子樹最大右端點 maxEnd。查詢時先檢查當前區間，再依左子樹的 maxEnd 判斷是否進入；若當前節點左端點已超過查詢右端點，右側也可停止。插入與刪除使用平衡樹操作，沿路徑更新 maxEnd，旋轉後重新計算受影響節點。」
分步驟深入解答
步驟 1：定義相交。 閉區間 [a,b] 與 [c,d] 相交當且僅當 a <= d 且 c <= b，並先拒絕 a > b。
步驟 2：定義節點。 節點包含 low、high、唯一 ID、左右子樹與 maxEnd；樹按 (low, id) 排序以容納重複端點。
步驟 3：查詢剪枝。 存取節點時回傳相交結果；只有左子樹 maxEnd >= query.low 才遞迴左側，且當前 low <= query.high 才可能進入右側。
步驟 4：維護增強欄位。 maxEnd 等於節點 high 與左右子樹 maxEnd 的最大值。插入、刪除和旋轉只需重算受影響路徑。
步驟 5：處理刪除。 以 ID 定位節點，執行平衡樹刪除，再由替換節點向上更新 maxEnd；不存在的 ID 回傳明確結果。
步驟 6：驗證邊界。 測試相鄰端點、完全包含、重複區間、負數、單點區間、空樹與全部相交的輸出規模。
步驟 7：說明複雜度。 平衡樹高度為對數級；查詢為 O(log n + k)（k 為輸出數），更新為 O(log n)，空間為 O(n)。
高品質示範回答
「我會用紅黑樹按 (low, id) 排序，每個節點保存 high 與子樹 maxEnd。查詢 [q1,q2] 時，若 low <= q2 且 high >= q1 就輸出；左子樹只有在 left.maxEnd >= q1 時進入，右子樹只有在當前 low <= q2 時進入。插入與刪除沿路徑更新最大值，紅黑樹旋轉後重算旋轉節點及父節點。重複區間用 ID 區分，測試閉區間端點與全部命中。查詢是 O(log n + k)，更新 O(log n)。」
常見錯誤
- 用
low < q2判斷相交 → 漏掉端點相接 → 依區間類型明確使用<=。 - 只保存節點的
high→ 無法剪枝 → 維護子樹maxEnd。 - 旋轉後不更新增強欄位 → 後續查詢錯誤 → 重算受影響節點。
- 把查詢複雜度寫成 O(log n) → 忽略輸出規模 → 寫成
O(log n + k)。 - 重複端點覆蓋舊節點 → 刪除與結果不穩定 → 使用唯一 ID 或複合鍵。
追問及應對
追問 1：只需要點查詢時怎麼最佳化？
把查詢區間設為 [x,x]，仍用 maxEnd 剪枝；若端點範圍很小且靜態，可評估專用離散結構。
追問 2：為什麼不用線性掃描？
區間數量大且更新、查詢交錯時，線性掃描每次要看全部節點；樹結構把搜尋降到輸出敏感範圍。
追問 3：旋轉為什麼不會破壞 maxEnd？
旋轉只改變局部子樹；按後序順序重算受影響節點即可維持欄位定義。
追問 4：如何刪除重複區間？
為每次插入分配 ID，鍵使用 (low, ID)，按 ID 定位並保留端點相同的其他區間。
追問 5：浮點端點怎麼辦？
明確 NaN、精度與相等語意；業務允許時優先轉成整數刻度或時間單位。
追問 6：結果要排序怎麼辦？
按樹序輸出可得到左端點順序；若剪枝存取順序不保證，收集後排序並說明額外成本。
追問 7：如何證明剪枝安全？
若左子樹最大右端點小於查詢左端點，左子樹所有區間右端點都更小，不可能相交，因此可安全跳過。