題目與範圍
實作半開區間 [left, right) 上的三個操作：增加覆蓋、判斷查詢區間是否完全覆蓋、移除覆蓋。可採用公開 Range Module 題目的約束 1 <= left < right <= 10^9 與最多 10^4 次呼叫。若介面允許防禦式輸入，需要說明 left >= right 的處理。
面試官考察什麼
核心是選擇並持續維護資料結構不變量。區間會被插入、移除和查詢，因此應保存依起點排序、互不相交的正規化區間；LeetCode 將有序集合和線段樹列為相關方向。Magicsheet 將此題標為 hard，並標示 ordered set 與 segment tree。題目也考察半開邊界、迭代器安全和複雜度核算。
先確認的澄清問題
- 端點是否包含？本文使用
[left, right)。 [1,3)與[3,5)是否合併？本文合併相鄰覆蓋。- 所有端點是否預先知道？基礎設計按線上呼叫處理。
left >= right怎麼辦？可直接返回且不改狀態，或明確拒絕。- 座標域是否有界且靜態？這決定是否採用線段樹。
分步解法
1. 表示方式與不變量
使用起點到終點的有序映射。std::map 保持鍵有序，並注明查找、插入、刪除為對數複雜度；升序迭代可只訪問附近區間。每次操作後正規化相鄰覆蓋，使 previousEnd >= nextStart 的情況不存在。
2. 新增覆蓋
從終點不小於 left 的第一個區間開始（也可先定位前驅）。只要目前起點不大於不斷擴大的 right，就更新左右邊界，並標記該節點刪除。刪除連續範圍後插入合併區間。空集合和與兩側都不相交的區間無需改變結構。
3. 移除與查詢
移除時遍歷符合 start < right 且 end > left 的區間。重疊區間保留 [oldStart,left)（若 oldStart < left）和 [right,oldEnd)（若 right < oldEnd），先刪除原節點再插入片段。查詢時檢查起點不大於 left 的最大起點區間；它存在且終點至少為 right 才回傳真。半開語義下 [1,3) 不覆蓋 [3,4)。
正確性與複雜度
不變量可用歸納法證明。新增操作把與新區間相連的所有區間替換成它們的聯集，因此不會遺失覆蓋且結果仍正規化。移除操作把每個重疊區間替換成移除範圍外的部分。查詢前驅足夠，因為排序且互不相交，任何更早區間的終點都不會更晚，任何更晚區間的起點又大於 left。
令 n 為區間數量，k 為一次更新觸碰的區間數。查詢為 O(log n)。更新包含 O(log n) 次定位，並進行 O(k) 的迭代和範圍刪除；若每個鍵都重新搜尋，則可能是 O(k log n)。空間為 O(n)。座標域已知且有限時可考慮線段樹；座標壓縮要求離線知道全部端點，不適合任意線上呼叫。
參考答案
“我會實作一個保存半開、排序、互不相交區間的正規化有序映射。新增定位並合併重疊或相鄰區間，移除移除重疊部分並保留至多兩個邊界片段，查詢檢查請求起點的前驅。證明重點是每個操作都保持正規化聯集。查詢 O(log n)，更新為 O(log n + k)（範圍迭代器刪除時），空間 O(n)。只有確認座標域和離線條件後，我才會比較線段樹。”
常見錯誤
- 把端點當作閉區間 → 相鄰區間被錯誤判為重疊 → 先定義
[left,right)。 - 保留相鄰區間 → 後續操作遇到重複結構 → 統一正規化相鄰覆蓋。
- 刪除後遞增失效迭代器 → 跳過節點或存取已釋放節點 → 保存下一個迭代器或刪除已知範圍。
- 切分時只保留一側 → 邊界覆蓋遺失 → 測試中間移除與完全包含。
- 聲稱更新始終 O(log n) → 一次操作可能觸碰多個區間 → 複雜度寫出
k。 - 線上使用座標壓縮 → 新端點無法映射 → 使用有序結構，或等待完整離線資料後重建。
延伸追問
應測試哪些邊界？
測試空模組、重複新增、恰好落在終點的查詢、先加 [1,3) 再加 [3,5)、移除中間片段、移除覆蓋整個區間、無重疊移除、巢狀區間，以及允許時的 0 和 10^9 端點。
如何驗證不變量？
每次隨機操作後斷言起點有序、end > start 且 previousEnd < nextStart。在小座標域中，把查詢結果與布林陣列或暴力聯集模型比較，可發現邊界和片段遺失問題。
什麼時候線段樹更合適？
座標域有界或可壓縮，且需要區間聚合或懶標記時可選線段樹。它提供穩定的對數操作，但節點和懶狀態更複雜；稀疏線上區間用有序映射更簡單。