区间树：日程调度员

算法背后的故事：被超额预订的房间

想象你管理着一间会议室。人们预订了不同的时间段：“上午 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)

小结

区间树教会我们：要管理时间，你需要追踪终点。通过简单地记住一组事件中“最晚的结束时间”，我们可以安全地忽略那些已成历史的巨大块。它提醒我们，效率来自于知道什么是已经“过去了的”。