解題說明
Range Module
題目描述：設計一個資料結構追蹤半開區間 [left, right)。支援三種操作：addRange 追蹤一個區間、queryRange 檢查某區間是否被完全追蹤、removeRange 移除追蹤的區間。
解題思路：使用 C++ 的 std::map 來維護一組不重疊的區間 {start -> end}。addRange(l, r) 時，找到所有與 [l, r) 重疊的區間，合併成一個大區間再插入。removeRange(l, r) 時，找到所有與 [l, r) 重疊的區間，切割或刪除受影響的部分。queryRange(l, r) 時，找到第一個 start <= l 的區間，檢查其 end 是否 >= r。利用 map 的有序性，所有操作可在 O(log n) + O(k) 時間內完成（k 為受影響的區間數）。
C++ 解法
複雜度分析
時間複雜度：addRange O(log n + k)、queryRange O(log n)、removeRange O(log n + k) — 其中 n 為當前區間數，k 為被合併/刪除的區間數。攤銷後每個操作為 O(log n)。
空間複雜度：O(n) — 最多存儲 n 個不重疊區間。
虛擬碼
1. Maintain sorted map: intervals (start -> end) 2. addRange(left, right): a. Find overlapping intervals (start <= right and end >= left) b. Merge: expand [left, right] to cover all overlapping intervals c. Remove all overlapping intervals, insert merged [left, right] 3. queryRange(left, right): a. Find the interval with largest start <= left b. Return true if its end >= right 4. removeRange(left, right): a. Find overlapping intervals b. For each: if it extends before left, keep [start, left); if after right, keep [right, end) c. Remove original overlapping intervals, add trimmed pieces
其他解法
線段樹（動態開點）：使用動態開點的線段樹，每個節點記錄區間是否被完全覆蓋。支援區間設值（addRange/removeRange）和區間查詢。時間 O(log C) 每操作（C 為值域），空間按需分配。適合值域很大的場景。
珠鍊排序（Sorted List of Endpoints）：用一個有序陣列記錄所有區間端點（標記開/閉）。每次操作時用二元搜尋定位並修改。概念更直觀但插入刪除的陣列操作為 O(n)。
延伸思考
- 如果操作非常頻繁（10^6 次），map 的常數因子是否會成為瓶頸？有更高效的替代方案嗎？
- 如何支援
countRange(left, right)回傳被追蹤的總長度？ - 若區間端點為浮點數，實作上需要注意什麼？