不相交区间树的高效区间管理

在处理区间查询和区间合并时，不相交区间树（Disjoint Interval Tree）是一种高效的数据结构。今天我们深入分析一个工业级 不相交区间树 的实现，探索其基于有序 map 的设计智慧。

场景与需求

不相交区间树的应用场景：

时间调度：管理不重叠的时间段
内存管理：跟踪已分配/空闲内存块
区间查询：快速判断点是否在某个区间内

核心需求：

高效插入：支持单个元素和区间插入
自动合并：相邻区间自动合并
高效查询：快速判断点是否存在
区间擦除：支持点擦除和区间擦除

解决方案：有序 Map 存储

工业级实现采用了巧妙的设计：

// 核心设计：使用有序 Map
using TTree = TMap<T, T>;  // key = 区间起点, value = 区间终点（不含）

// 不变式：区间永不重叠

核心设计

区间表示
- 区间 [a, b) 表示为 (a, b)
- key = 起点，value = 终点（不含）
- 所有区间按起点排序，永不重叠

插入合并

// 尝试扩展左区间
if (p != Tree.end() && p->second == begin) {
    p->second = end;
    // 尝试合并相邻区间
    if (next != Tree.end() && next->first == end) {
        p->second = next->second;
        Tree.erase(next);
    }
}

点查询

// 找到第一个起点 > t 的区间，然后检查前一个
TIterator l = Tree.lower_bound(t);
if (l != Tree.begin()) {
    --l;
    if (l->first < t && t < l->second) {
        return l;  // 找到
    }
}

区间擦除
- 可能需要分割区间
- 处理三种情况：擦除起点、擦除终点、中间擦除

权衡分析

优点

O(log n) 查找：利用 map 的有序性
自动合并：相邻区间自动合并
空间高效：区间数量远少于元素数量时优势明显
操作简洁：支持丰富的区间操作

代价

内存开销：需要存储 map 节点
实现复杂：区间合并和分割逻辑复杂
不变式维护：必须保证区间永不重叠

适用场景

需要频繁查询点是否在区间内
区间数量远少于元素数量
需要高效的区间合并

净室重构：Python 实现

下面用 Python 展示同样的设计思想：

class DisjointIntervalTree:
    """不相交区间树"""
    
    def __init__(self):
        self.intervals = []  # sorted list of (start, end)
        self.num_elements = 0
    
    def insert_interval(self, begin, end):
        """插入区间 [begin, end)"""
        # 尝试与左右相邻区间合并
        # ...
    
    def has(self, t):
        """检查点是否存在"""
        idx = bisect_left(self.intervals, (t + 1, float('inf'))) - 1
        if idx >= 0:
            start, inter_end = self.intervals[idx]
            return start <= t < inter_end
        return False
    
    def erase(self, t):
        """擦除单个点，可能分割区间"""
        # 找到所在区间，根据位置分割
        # ...

运行结果验证了设计：

=== Disjoint Interval Tree Demo (Python) ===

--- Test 1: Insert Elements ---
Insert 5: [(5, 6)], elements=1
Insert 1: [(1, 2), (5, 6)], elements=2
Insert 3: [(3, 4), (1, 2), (5, 6)], elements=3

--- Test 2: Has ---
Has 1: True
Has 3: True
Has 10: False

--- Test 3: Erase ---
Before erase 3: [(1, 2), (3, 4), (5, 6)]
After erase 3: [(1, 2), (5, 6)]

总结

不相交区间树的设计体现了 简洁与高效的平衡：

有序 map：用空间换时间，O(log n) 查找
自动合并：插入时智能合并相邻区间
区间分割：擦除时正确处理三种情况
不重叠不变式：简化查询逻辑

这种设计不是"银弹"，但对于区间管理场景，是一个非常优雅的权衡选择。