Range Module 如何用有序区间维护 add、query 和 remove？

简化版

Range Module 可以用 TreeMap 维护一组不重叠半开区间 [l,r)，key 为左端点，value 为右端点。addRange 合并所有相交或相邻区间；queryRange 找左端点不大于 left 的区间看是否覆盖到 right；removeRange 删除覆盖部分，必要时把原区间拆成左右两段。

详细版

有序区间维护的核心是通过 floorEntry 找可能覆盖左端的区间，通过 ceilingEntry 或迭代扫描后续相交区间。添加区间时，不断合并所有 start <= right 且 end >= left 的区间；删除区间时，先保存可能被切开的左右残段，再删除中间所有相交区间。

每次操作复杂度约为 O(k log n)，其中 k 是被合并或删除的区间数。端点是半开语义，[1,3) 和 [3,5) 可以合并也可以保持相邻，具体看实现需求。

完整版教学

一、Range Module 维护的是什么

它维护一组已经被追踪的数轴区间，支持：

addRange(left, right)
queryRange(left, right)
removeRange(left, right)

常见语义是半开区间 [left,right)。内部最好始终保持区间有序且互不重叠，这样查询和更新才可控。

二、为什么用 TreeMap

TreeMap 按左端点排序，能快速找到某个位置左侧最近区间：

floorEntry(x)：起点 <= x 的最右区间
ceilingEntry(x)：起点 >= x 的最左区间

操作	需要能力
查询覆盖	找 left 左侧可能覆盖它的区间
添加合并	找所有和新区间相交的区间
删除拆分	找所有被删除区间影响的区间

记忆钩子：动态区间题，TreeMap 管“相邻区间在哪里”。

三、queryRange 为什么只看 floorEntry

要判断 [left,right) 是否完全被覆盖，只可能由起点不大于 left 的某个区间覆盖。因为内部区间不重叠，如果这个区间都覆盖不到 right，后面的区间起点更大，中间会断。

entry = floorEntry(left)
存在且 entry.end >= right => true
否则 false

这个查询是 O(log n)，也是保持区间不重叠带来的收益。

四、addRange 如何合并

添加 [left,right) 时，先看左侧区间是否和它相交或相邻；若相交，就扩展新区间边界并删除旧区间。然后继续处理起点不大于当前 right 的后续区间。

已有：[1,3), [5,8)
添加：[2,6)
合并后：[1,8)

合并过程里，新的 left 是所有相关区间左端最小值，新的 right 是最大右端。

五、removeRange 如何拆区间

删除 [left,right) 时，一个原区间可能被切成左右两段：

原：[1,10)
删：[3,7)
剩：[1,3), [7,10)

实现时可以先记录：

如果原区间 start < left，保留 [start,left)
如果原区间 end > right，保留 [right,end)

然后删除所有相交区间，再把残段放回 TreeMap。

六、代码骨架

class RangeModule {
    TreeMap<Integer, Integer> map = new TreeMap<>();

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> e = map.floorEntry(left);
        return e != null && e.getValue() >= right;
    }

    public void addRange(int left, int right) {
        Map.Entry<Integer, Integer> e = map.floorEntry(left);
        if (e != null && e.getValue() >= left) {
            left = Math.min(left, e.getKey());
            right = Math.max(right, e.getValue());
            map.remove(e.getKey());
        }
        e = map.ceilingEntry(left);
        while (e != null && e.getKey() <= right) {
            right = Math.max(right, e.getValue());
            map.remove(e.getKey());
            e = map.ceilingEntry(left);
        }
        map.put(left, right);
    }
}

removeRange 代码更长，但核心就是“找相交、删旧段、补残段”。

七、常见误区与追问

误区：用数组标记每个点。 坐标范围通常很大，必须维护区间而不是点。
误区：query 时检查多个区间拼接。 Range Module 内部不重叠，完整覆盖必须由一个包含 left 的区间覆盖到 right。
误区：remove 时忘记拆成两段。 删除中间会产生左右残段。
追问：为什么是半开区间？ 半开区间更适合表达连续范围，端点拼接不重叠。
追问：add 时相邻区间要合并吗？ 半开语义下可合并 [1,3) 和 [3,5) 为 [1,5)，查询效果等价。
追问：复杂度是多少？ 与受影响区间数有关，通常是 O(k log n)。

八、加强记忆

Range Module 的心法是“始终维护有序不重叠区间”。查询找 floorEntry(left) 看能否盖到 right；添加把所有碰到的区间吞成一个大区间；删除则切掉中间，必要时补回左右残段。TreeMap 不是装饰，它是快速定位左右邻居的核心工具。

简化版

详细版