区间树Interval tree

为区间集合维护可剪枝的边界信息。

常见操作#

n 为区间数，k 为命中数；这里区分增强搜索树与静态中心区间树。

操作	时间复杂度	条件与说明
增强平衡树：插入 / 删除	$O(\log n)$	按区间起点排序，节点维护子树最大终点，旋转后更新增广信息。
增强平衡树：找一个相交区间	$O(\log n)$	用子树最大终点剪枝；底层树保持平衡。
增强平衡树：枚举所有相交区间	最坏 $O(n)$	具体输出界取决于增广、查询类型与遍历方式；不能把所有区间树都写成 $O(\log n+k)$ 。
静态中心区间树：点刺查询	$O(\log n+k)$	每节点保存按左右端点分别排序的跨中心区间；这是另一种表示。

相交区间数量本身可达到 n；“找到一个”与“报告全部”应分开比较。

基础原理参考资料

Linux 6.12 · Augmented rbtree interval examplemax endpoint 增广、区间相交查找与更新回调。

CGAL · Interval Skip List对照另一类区间报告结构，说明输出规模和随机化前提。

David Mount · Interval Trees课程讲义第 147 页起：按中心划分、左右端点列表与点刺查询的输出敏感界。