区间树如何基于平衡搜索树查询重叠区间？

简化版

区间树通常用平衡 BST 按区间左端点排序，并在每个节点维护子树中最大的右端点 maxEnd。查询区间 [l,r] 时，若当前节点重叠就返回；否则根据左子树 maxEnd 判断左边是否可能有重叠，没有就去右边。

详细版

每个节点保存：

interval=[start,end]；
按 start 作为 BST key；
maxEnd = max(end, left.maxEnd, right.maxEnd)。

查询某个区间 q=[l,r]：

若当前节点区间和 q 重叠，命中；
若左子树存在且 left.maxEnd >= l，左子树可能有区间右端能碰到 q，去左边；
否则左子树所有区间都在 q 左侧结束，只能去右边。

如果底层树保持平衡，插入、删除、查询一个重叠区间通常是 O(log n)，最坏仍取决于输出数量和树形。

完整版教学

一、区间树解决什么问题

普通 BST 擅长按单个 key 查找，但区间查询有两个端点。比如已有会议 [1,4]、[6,9]、[10,12]，新会议 [3,5] 是否冲突？只按左端点排序，不能直接二分出答案，因为一个很早开始但很晚结束的区间也可能重叠。

区间树的做法是仍然按左端点建立平衡 BST，但额外维护每棵子树的最大右端点 maxEnd。它让我们知道某个方向是否还有可能碰到查询区间。

记忆钩子：start 负责排序，maxEnd 负责告诉你「这片子树最远能伸到哪里」。

二、重叠判断是什么

两个闭区间 [a,b] 和 [c,d] 重叠，当且仅当：

a <= d && c <= b

也就是一个区间的开始不在另一个区间结束之后。若使用半开区间 [start,end)，判断要改成 a < d && c < b。会议日程类题目常用半开区间，这个边界要提前问清。

带数字例子：[3,5] 和 [5,8] 在闭区间语义下重叠，在半开区间语义下不重叠。边界语义会直接改变代码比较符。

三、maxEnd 为什么能剪枝

假设查询区间是 [l,r]。若当前节点左子树的 maxEnd < l，说明左子树中所有区间的右端点都小于 l。它们全都在查询区间左侧结束，不可能与 [l,r] 重叠，因此左子树可以整棵跳过。

反过来，如果 left.maxEnd >= l，左子树至少存在某个区间右端点伸到 l 以后，它可能重叠，值得优先搜索左边。

条件	含义	决策
`left.maxEnd < q.start`	左边都结束太早	跳过左子树
`left.maxEnd >= q.start`	左边可能碰到查询	搜左子树
当前区间重叠	已找到答案	返回或收集

这个剪枝是区间树比普通遍历快的核心。

四、代码框架

查找任意一个重叠区间的伪代码如下：

Node searchOverlap(Node root, int l, int r) {
    Node x = root;
    while (x != null && !overlap(x.start, x.end, l, r)) {
        if (x.left != null && x.left.maxEnd >= l) {
            x = x.left;
        } else {
            x = x.right;
        }
    }
    return x;
}

插入删除后，沿路径和旋转涉及的节点都要重新计算 maxEnd。如果底层是红黑树或 AVL，旋转后同样要先更新下沉节点，再更新上升节点。

五、输出所有重叠区间怎么办

如果只找任意一个重叠区间，搜索路径通常接近 O(log n)。如果要输出所有重叠区间，就不能找到一个就停，需要递归搜索所有可能方向。复杂度常写成 O(log n + k) 的目标形式，k 是输出个数，但实现细节和树形会影响常数。

输出所有时可以用剪枝：

若 node.left.maxEnd >= q.start，左边可能有结果
若 node.start <= q.end，右边可能还有 start 不太大的区间
当前节点重叠则加入答案

查询越宽，输出 k 越大，任何结构都至少要花 O(k) 时间。

六、和线段树有什么区别

区间树存的是一组动态区间对象，适合插入删除区间并查重叠。线段树通常维护固定坐标轴上的覆盖、最大值、区间加等聚合信息。两者名字都带树，但操作模型不同。

结构	适合问题	key 空间	动态性
区间树	查已有区间是否与新区间重叠	可稀疏	区间对象动态增删
线段树	固定范围区间更新/查询	常需离散化或固定范围	更新值或覆盖
TreeMap 扫邻居	简单日程无重叠插入	按 start 排序	只查相邻即可

面试中如果只是 My Calendar I，TreeMap 查前后邻居就够；如果要通用重叠查询，区间树更系统。

七、常见误区与追问

误区：区间树按右端点排序。 常见实现按左端点排序，右端点通过 maxEnd 增强。
追问：maxEnd 的作用是什么？ 判断某棵子树是否可能有区间伸到查询起点之后。
误区：闭区间和半开区间比较符一样。 边界相接是否重叠会改变 < 和 <=。
追问：旋转后 maxEnd 怎么维护？ 和 size 一样，先更新下沉节点，再更新上升节点。
误区：找到一个重叠区间和找所有重叠区间复杂度一样。 输出所有至少需要 O(k)。

八、加强记忆

区间树是「按 start 排序的平衡树 + maxEnd 增强字段」。当前节点用区间重叠公式判断，左子树用 maxEnd 判断能不能剪掉。它适合动态区间集合的重叠查询，不要和线段树混成一类。边界语义要先确认：闭区间相接算重叠，半开区间相接通常不算。

简化版

详细版