题目与使用场景
区间树适合动态时间段、预约和资源占用查询。关键是用按左端点排序的平衡树保存区间，并在每个子树维护最大右端点，从而跳过不可能相交的分支。
面试官考察什么
- 是否准确处理闭区间边界与相交条件。
- 是否说明
maxEnd的定义和维护范围。 - 是否利用增强字段剪枝，而不是遍历全部节点。
- 是否在旋转、插入和删除后更新增强字段。
- 是否处理重复区间、空树和删除不存在元素。
- 是否给出输出敏感的时间复杂度。
作答前的澄清问题
- 区间是闭区间、开区间还是半开区间？
- 端点类型是整数、浮点还是时间戳？
- 重复区间是否允许，删除按 ID 还是按端点匹配？
- 查询需要全部结果还是只要一个相交区间？
- 是否要求在线插入删除和自平衡？
- 结果顺序是否必须按左端点排序？
30 秒回答框架
“我以区间左端点为树键，每个节点保存右端点和子树最大右端点 maxEnd。查询时先检查当前区间是否相交，再根据左子树的 maxEnd 判断是否值得进入；若当前节点左端点已超过查询右端点，右侧也可停止。插入和删除使用平衡树操作，并沿路径更新 maxEnd，旋转后重新计算受影响节点。”
分步骤深入解答
步骤 1：定义相交。 闭区间 [a,b] 与 [c,d] 相交当且仅当 a <= d 且 c <= b，先约束非法的 a > b。
步骤 2：定义节点。 节点包含 low、high、唯一 ID、左右子树和 maxEnd；树按 (low, id) 排序以容纳重复端点。
步骤 3：查询剪枝。 访问节点时报告相交结果；只有左子树 maxEnd >= query.low 才递归左侧，且当前 low <= query.high 时才可能访问右侧。
步骤 4：维护增强字段。 maxEnd 等于节点 high 与左右子树 maxEnd 的最大值。插入、删除和旋转只需重算受影响路径。
步骤 5：处理删除。 通过 ID 定位节点，执行平衡树删除，再从替换节点向上更新 maxEnd；不存在的 ID 返回明确结果。
步骤 6：验证边界。 测试相邻端点、完全包含、重复区间、负数、单点区间、空树和全部相交的输出规模。
步骤 7：说明复杂度。 平衡树高度为对数级；查询成本为 O(log n + k)（k 为输出数），更新为 O(log n)，空间为 O(n)。
高质量示范回答
“我会用红黑树按 (low, id) 排序，每个节点保存 high 和子树 maxEnd。查询 [q1,q2] 时，若 low <= q2 且 high >= q1 就输出；左子树只有在 left.maxEnd >= q1 时进入，右子树只有在当前 low <= q2 时进入。插入和删除沿路径更新最大值，红黑树旋转后重算旋转节点及其父节点。重复区间用 ID 区分，测试闭区间端点和全部命中场景。查询是 O(log n + k)，更新 O(log n)。”
常见错误
- 用
low < q2判断相交 → 漏掉端点相接 → 按区间类型明确使用<=。 - 只保存节点的
high→ 无法剪枝 → 维护子树maxEnd。 - 旋转后不更新增强字段 → 后续查询错误 → 重算受影响节点。
- 把查询复杂度写成 O(log n) → 忽略输出规模 → 写成
O(log n + k)。 - 重复端点覆盖旧节点 → 删除和结果不稳定 → 使用唯一 ID 或复合键。
追问及应对
追问 1：只需要点查询时怎么优化？
把查询区间设为 [x,x]，仍使用 maxEnd 剪枝；若端点范围很小且静态，可评估专用离散结构。
追问 2：为什么不用线性扫描？
区间数量大且更新、查询交错时，线性扫描每次要看全部节点；树结构把搜索成本降到输出敏感范围。
追问 3：旋转为什么不会破坏 maxEnd？
旋转只改变局部子树；按后序顺序重算受影响节点即可保持字段定义。
追问 4：如何删除重复区间？
为每个插入分配 ID，键使用 (low, ID)，删除按 ID 定位并保留端点相同的其他区间。
追问 5：浮点端点怎么办？
明确 NaN、精度和相等语义；若业务允许，优先转换为整数刻度或时间单位。
追问 6：结果要排序怎么办？
按树序输出可得到左端点顺序；若剪枝访问顺序不满足要求，收集后再排序并说明额外成本。
追问 7：如何证明剪枝安全？
若左子树最大右端点小于查询左端点，左子树所有区间的右端点都更小，不可能相交，因此可安全跳过。