海量不重叠区间场景下查询目标区间是否被覆盖的合适数据结构选型

该场景下优先选择基于有序边界点标记的平衡搜索树方案，完全符合enclose()优先级更高的要求，两个操作时间复杂度均为O(logn)，可轻松支撑百万级区间的处理需求。

核心设计思路 #

因为输入的所有原始区间互不重叠，且查询区间的边界必然和输入区间的边界重合，我们可以把所有合并后的连续区间的端点存入平衡搜索树，每个端点标记为「区间左端点(START)」或「区间右端点(END)」。合并后的区间天然满足START和END交替出现的规律，不存在连续的START或END节点。

操作逻辑说明 #

enclose(i) 查询（O(logn)，性能最优） #

给定查询区间[a, b)：

1. 找到树中小于等于a的最大边界点
2. 如果该点不是START标记，说明a不在已覆盖的区间内，直接返回False
3. 找到该START对应的下一个边界点（即当前覆盖区间的右端点），如果该右端点 >= b，说明查询区间完全被覆盖，返回True，否则返回False

add(c) 插入（O(logn)） #

给定新增区间[a, b)：

1. 处理左端点a：如果a已在树中且为END标记，说明a刚好是前一个已存区间的右端点，可直接合并，删除该END节点即可；如果a不在树中，插入标记为START的a节点
2. 处理右端点b：如果b已在树中且为START标记，说明b刚好是后一个已存区间的左端点，可直接合并，删除该START节点即可；如果b不在树中，插入标记为END的b节点

可直接落地的Python实现 #

Python场景下无需手动实现红黑树，可直接使用sortedcontainers库的SortedDict（底层为跳表，所有操作均为O(logn)性能），实现代码如下：

from sortedcontainers import SortedDict

START = 1
END = 0

class IntervalSet:
    def __init__(self):
        # key为区间边界值，value为对应边界标记
        self.boundary = SortedDict()
    
    def add(self, interval: list[int, int]):
        left, right = interval
        # 处理左端点
        if left in self.boundary:
            if self.boundary[left] == END:
                # 和前序区间接壤，删除端点即可合并
                del self.boundary[left]
        else:
            self.boundary[left] = START
        # 处理右端点
        if right in self.boundary:
            if self.boundary[right] == START:
                # 和后序区间接壤，删除端点即可合并
                del self.boundary[right]
        else:
            self.boundary[right] = END
    
    def enclose(self, query: list[int, int]) -> bool:
        q_left, q_right = query
        # 找小于等于查询左边界的最大节点
        idx = self.boundary.bisect_right(q_left) - 1
        if idx < 0:
            return False
        cur_val, cur_flag = self.boundary.peekitem(idx)
        # 左边界不在已覆盖区间内
        if cur_flag != START:
            return False
        # 获取当前覆盖区间的右端点
        cur_interval_right = self.boundary.peekitem(idx + 1)[0]
        return cur_interval_right >= q_right

测试示例 #

if __name__ == "__main__":
    my_set = IntervalSet()
    my_set.add([2,4])
    my_set.add([0,2])
    print(my_set.enclose([0,4])) # 输出 True

方案优势对比 #

相比区间树、线段树等其他区间处理数据结构，该方案实现简单、内存占用更低，且enclose()操作仅需两次logn级别的查询，完全满足高优先级的性能要求。

内容的提问来源于stack exchange，提问作者dontloo