演算法筆記：區間搜尋樹（Interval Search Tree）完整設計與操作

問題定義

給定一組區間 [lo, hi]，支援操作：

• put(lo, hi, value)：插入區間
• get(lo, hi)：查找完全匹配區間
• delete(lo, hi)：刪除區間
• intersect(lo, hi)：回傳所有與查詢區間相交的區間

資料結構：區間搜尋樹（基於 BST 增強）

• 鍵值：區間起點 lo
• 值：區間終點 hi + 附屬資料
• 增強欄位：maxHi = 子樹中最大的 hi

核心操作：插入

標準 BST 插入（按 lo），插入後向上回溯更新祖先節點的 maxHi。

核心操作：相交查詢

// 回傳任一相交區間（或收集所有）
Node* intersect(Node* root, int lo, int hi) {
    if (!root) return nullptr;
    // 1. 當前節點相交？
    if (root->lo <= hi && lo <= root->hi) return root;
    // 2. 左子樹最大 hi < lo → 左子樹不可能相交
    if (root->left && root->left->maxHi >= lo)
        return intersect(root->left, lo, hi);
    // 3. 否則往右子樹
    return intersect(root->right, lo, hi);
}

關鍵剪枝：若左子樹 maxHi < lo，則左子樹所有區間終點都在查詢區間起點左側，不可能相交，直接捨棄。

刪除操作

標準 BST 刪除（三種情況：葉子、單子樹、雙子樹找前驅/後繼），刪除後回溯更新 maxHi。

複雜度分析

實作建議

1. 使用 std::map 或自製紅黑樹作為底層 BST
2. 節點結構體包含 lo, hi, value, maxHi, left, right, parent
3. 更新 maxHi 寫成獨立函式 updateMaxHi(Node*)，插入/刪除後呼叫
4. intersectAll 收集所有結果時，繼續搜尋另一邊子樹（不早返回）