區間樹：日程調度員

演算法背後的故事：被超額預訂的房間

想像妳管理著一間會議室。人們預訂了不同的時間段：「上午 9 點到 11 點」，「上午 10 點到 12 點」，「下午 1 點到 2 點」。 一個新的請求進來了：「我可以預訂上午 10:30 到 11:30 嗎？」

要回答這個問題，妳不能只看開始時間。9 點的會議開始於 10:30 之前，但它結束於 11:00，所以它重疊了。10 點的會議也重疊了。

如果妳有 1000 個預訂，逐一檢查 ($O(N)$) 太慢了。妳需要一種能理解「跨度」和「持續時間」的結構。

這就是 區間樹 (Interval Tree)。它是一種特殊的二叉搜尋樹 (BST)，儲存範圍 $[start, end]$，並能在 $O(\log N)$ 時間內回答：「有人跟我重疊嗎？」

為什麼需要它？

• 日曆： 「Luke 在下午 2 點到 4 點之間有空嗎？」
• 生物資訊學： 「這個新的基因序列是否與 DNA 中任何已知的疾病標記重疊？」
• 視窗管理： 「滑鼠在位置 (X, Y) 點擊了桌面上的哪些視窗？」

演算法是如何「思考」的

這個演算法是一個基於中心的組織者。

1. 骨架： 它的行為像普通的 BST，根據區間的 low (開始) 值進行排序。
2. 增強 (Augmentation)： 這是秘方。每個節點儲存一條額外資訊：其整個子樹的 最大結束時間 (Max High)。

搜尋邏輯 (與 $[L, R]$ 有重疊嗎？)：

• 從根節點開始。
• 當前節點重疊嗎？如果是，返回它。
• 向左走？ 如果左孩子的 max 大於我的 $L$，這意味著下面有東西延伸得足夠遠，可能會碰到我。我們必須檢查左邊。
• 向右走？ 否則，向右走。

這個簡單的「最大值」允許我們忽略樹中那些「結束得太早」而無關緊要的整個分支。

工程決策：線段樹 vs. 區間樹

工程師經常混淆這兩者：

• 區間樹 (Interval Tree)： 儲存實際的區間（例如具體的會議）。用於區間是動態的且妳需要尋找重疊的場景。
• 線段樹 (Segment Tree)： 將空間劃分為固定的片段。用於「範圍查詢」（例如「陣列索引 5 到 100 之間的元素之和是多少？」）。

實作參考 (Python)

class IntervalNode:
    def __init__(self, low, high):
        self.low = low
        self.high = high
        self.max = high # 該子樹中的最大結束時間
        self.left = None
        self.right = None

def insert(node, low, high):
    if not node:
        return IntervalNode(low, high)
    
    # 基於 'low' 的標準 BST 插入
    if low < node.low:
        node.left = insert(node.left, low, high)
    else:
        node.right = insert(node.right, low, high)
    
    # 更新此節點的最大值
    if node.max < high:
        node.max = high
        
    return node

def search_overlap(node, low, high):
    if not node:
        return None
    
    # 檢查當前節點是否重疊
    if node.low <= high and low <= node.high:
        return (node.low, node.high)
    
    # 如果左孩子的最大值大於我們的 low，
    # 答案可能在左子樹中。
    if node.left and node.left.max >= low:
        return search_overlap(node.left, low, high)
    
    return search_overlap(node.right, low, high)

# 使用範例
root = None
bookings = [(15, 20), (10, 30), (17, 19), (5, 20), (12, 15), (30, 40)]
for l, h in bookings:
    root = insert(root, l, h)

# 檢查重疊
query = (14, 16)
print(f"與 {query} 重疊的區間: {search_overlap(root, *query)}")
# 根據結構可能返回 (5, 20) 或 (10, 30)

小結

區間樹教會我們：要管理時間，妳需要追蹤終點。透過簡單地記住一組事件中「最晚的結束時間」，我們可以安全地忽略那些已成歷史的巨大塊。它提醒我們，效率來自於知道什麼是已經「過去了的」。