题目与范围
实现半开区间 [left, right) 上的三个操作：增加覆盖、判断查询区间是否完全覆盖、删除覆盖。可采用公开 Range Module 题目的约束 1 <= left < right <= 10^9 与最多 10^4 次调用。若接口允许防御式输入，需要说明 left >= right 的处理。
面试官考察什么
核心在于选择并持续维护数据结构不变量。区间会被插入、删除和查询，因此应保存按起点排序、互不相交的规范化区间；LeetCode 将有序集合和线段树列为相关方向。Magicsheet 将该题标为 hard，并标注 ordered set 与 segment tree。题目还考察半开边界、迭代器安全和复杂度核算。
先确认的澄清问题
- 端点是否包含？本文使用
[left, right)。 [1,3)与[3,5)是否合并？本文合并相邻覆盖。- 所有端点是否预先已知？基础设计按在线调用处理。
left >= right怎么办？可以直接返回且不改状态，或显式拒绝。- 坐标域是否有界且静态？这决定是否采用线段树。
分步解法
1. 表示方式与不变量
使用起点到终点的有序映射。std::map 保持键有序，并注明查找、插入、删除为对数复杂度；升序迭代可只访问附近区间。每次操作后规范化相邻覆盖，使 previousEnd >= nextStart 的情况不存在。
2. 添加覆盖
从终点不小于 left 的第一个区间开始（也可先定位前驱）。只要当前起点不大于不断扩大的 right，就更新左右边界，并标记该节点删除。删除连续范围后插入合并区间。空集合和与两侧都不相交的区间无需改变结构。
3. 删除与查询
删除时遍历满足 start < right 且 end > left 的区间。重叠区间保留 [oldStart,left)（若 oldStart < left）和 [right,oldEnd)（若 right < oldEnd），先删除原节点再插入片段。查询时检查起点不大于 left 的最大起点区间；它存在且终点至少为 right 才返回真。半开语义下 [1,3) 不覆盖 [3,4)。
正确性与复杂度
不变量可以用归纳法证明。添加操作把与新区间相连的所有区间替换成它们的并集，因此不会丢失覆盖且结果仍规范化。删除操作把每个重叠区间替换成移除范围外的部分。查询前驱足够，因为排序且互不相交，任何更早区间的终点都不会更晚，任何更晚区间的起点又大于 left。
令 n 为区间数量，k 为一次更新触碰的区间数。查询为 O(log n)。更新包含 O(log n) 次定位，并进行 O(k) 的迭代和范围删除；若每个键都重新搜索，则可能是 O(k log n)。空间为 O(n)。坐标域已知且有限时可考虑线段树；坐标压缩要求离线知道全部端点，不适合任意在线调用。
参考答案
“我会实现一个保存半开、排序、互不相交区间的规范化有序映射。添加定位并合并重叠或相邻区间，删除移除重叠部分并保留至多两个边界片段，查询检查请求起点的前驱。证明重点是每个操作都保持规范化并集。查询 O(log n)，更新为 O(log n + k)（范围迭代器删除时），空间 O(n)。只有确认坐标域和离线条件后，我才会比较线段树。”
常见错误
- 把端点当作闭区间 → 相邻区间被错误判为重叠 → 先定义
[left,right)。 - 保留相邻区间 → 后续操作遇到重复结构 → 统一规范化相邻覆盖。
- 删除后递增失效迭代器 → 跳过节点或访问已释放节点 → 保存下一个迭代器或删除已知范围。
- 切分时只保留一侧 → 边界覆盖丢失 → 测试中间删除与完全包含。
- 声称更新始终 O(log n) → 一次操作可能触碰多个区间 → 复杂度写出
k。 - 在线使用坐标压缩 → 新端点无法映射 → 使用有序结构，或等待完整离线数据后重建。
延伸追问
应测试哪些边界？
测试空模块、重复添加、恰好落在终点的查询、先加 [1,3) 再加 [3,5)、删除中间片段、删除覆盖整个区间、无重叠删除、嵌套区间，以及允许时的 0 和 10^9 端点。
如何验证不变量？
每次随机操作后断言起点有序、end > start 且 previousEnd < nextStart。在小坐标域中，把查询结果与布尔数组或暴力并集模型比较，可发现边界和片段丢失问题。
什么时候线段树更合适？
坐标域有界或可压缩，且需要区间聚合或懒标记时可选线段树。它提供稳定的对数操作，但节点和懒状态更复杂；稀疏在线区间用有序映射更简单。