解題說明
Data Stream as Disjoint Intervals
題目描述：設計一個 SummaryRanges 類別，支援兩個操作：addNum(val) 將整數 val 加入資料流；getIntervals() 回傳所有不相交的閉合區間（升序排列），涵蓋目前資料流中所有數字。
解題思路：使用 std::map<int,int> intervals，以區間起點（start）為 key，終點（end）為 value，維護所有不相交區間集合。
addNum(val) 執行步驟：
- 先檢查
val是否已在某個現有區間內，若是則直接返回（避免重複處理）。 - 找右鄰：
auto right = intervals.lower_bound(val)——第一個 start ≥ val 的區間。 - 找左鄰：若
right != begin()，則left = prev(right)——start < val 的最近區間。 - 判斷是否可與左鄰合併：若
left->second >= val - 1，表示左鄰的 end ≥ val-1，新數字緊貼或重疊左鄰。 - 判斷是否可與右鄰合併：若
right->first <= val + 1，表示右鄰的 start ≤ val+1，新數字緊貼或重疊右鄰。 - 根據以上判斷做四種情況處理：僅左合併、僅右合併、左右都合併（三者連成一個大區間）、無合併（插入新的單點區間 [val, val]）。
C++ 解法
複雜度分析
時間複雜度：addNum — O(log n)，其中 n 為目前不相交區間數量（map 的 lower_bound 和 erase 均為 O(log n)）；getIntervals — O(k)，k 為區間數量。
空間複雜度：O(n) — map 儲存最多 n 個不相交區間（n 為加入的不同數字個數）。
虛擬碼
addNum(val):
right = first interval with start >= val
if left neighbor exists and left.end >= val: return (already covered)
mergeLeft = left neighbor exists AND left.end >= val - 1
mergeRight = right exists AND right.start <= val + 1
if mergeLeft AND mergeRight:
left.end = max(left.end, right.end)
erase right
else if mergeLeft:
left.end = max(left.end, val)
else if mergeRight:
newEnd = right.end; erase right; insert [val, newEnd]
else:
insert [val, val]
getIntervals():
for each (start, end) in map:
append [start, end] to result
return result其他解法
有序集合 + 二分搜尋（TreeSet）：在 Java 中可用 TreeSet 配合 floor/ceiling 操作，原理相同，但 C++ 的 std::map 已是此模式的最佳實踐。
排序陣列 + 每次 getIntervals 合併：每次 addNum 只將值塞入一個 unordered_set，每次 getIntervals 時取出所有值排序並線性合併。優點是 addNum 為 O(1)，缺點是 getIntervals 為 O(n log n)，適合寫多讀少的場景。
線段樹 / 二元索引樹（BIT）：在值域範圍固定（如 0～10⁴）時，可用線段樹維護覆蓋區間，addNum 和 getIntervals 均為 O(log V)，適合值域小但呼叫頻繁的場景。
延伸思考
- 若需支援
removeNum(val)操作，std::map的設計應如何修改？ - 若資料流中的數字值域極大（如 0～10⁹），但數字個數 n 很小，本解法效率如何？與值域壓縮法比較。
- 若
getIntervals呼叫頻率遠低於addNum，選擇哪種實作方式更好？請分析時間與空間的取捨。