区间树 | Codeboy's Blog

选定版本与端点约定

“Interval tree”有多种结构。本页选 centered interval tree，并固定闭区间 $I=[low(I),high(I)]$ ；端点相等或只在端点接触也算相交。重复区间以独立 interval-id 保存，删除必须指定实例。

树节点有中心值 $c$ 。所有包含 $c$ 的区间存于该节点：一份按 low 递增，一份按 high 递减；满足 $high<c$ 的区间递归进入左子树，满足 $low>c$ 的进入右子树。每个区间恰好归属一个节点，两份列表只存同一实例的引用。

以下动态保证假设可能出现的端点坐标集预先已知，据此建立高度 $O(\log n)$ 的固定中心骨架；活动区间可以任意插入删除。每个节点的两张端点表用平衡搜索树维护，空间 $O(n)$ ，更新最坏 $O(\log n)$ 。若坐标宇宙也动态扩张，需局部重建中心骨架，保证相应变为摊还。

查询点 $q$ 。在中心 $c$ ：

若 $q<c$ ，扫描按 low 递增的列表，报告所有 $low\le q$ ，遇首个 $low>q$ 停止；这些区间都含 $c>q$ ，故无需再检查 high。随后只递归左子树。
若 $q>c$ ，对按 high 递减列表对称扫描至 $high<q$ ，随后只递归右子树。
若 $q=c$ ，节点存放的全部区间都命中，子树不可能含 $c$ 。

搜索只走一条高度 $O(\log n)$ 的中心路径，列表扫描的每个元素都实际输出，所以报告 $k$ 个区间的最坏时间为

O(\log n+k).

查询闭区间 $Q=[l,r]$ 。若 $r<c$ ，当前节点只需从 low-list 报告 $low\le r$ 的前缀，再递归左侧；若 $l>c$ ，从 high-list 报告 $high\ge l$ 的前缀，再递归右侧。

若 $l\le c\le r$ ，当前节点全部区间都与 $Q$ 相交，并递归两侧。每个被展开的跨中心节点至少报告一个此前未报告的归属区间，边界搜索路径另有 $O(\log n)$ 个节点，故总报告时间仍为 $O(\log n+k)$ 。

活动区间为

[9,11],\ [10,12],\ [13,15],\ [14,17].

查询新会议 $[11,14]$ 时，闭区间约定下四项都冲突：前两项在端点 $11$ 相交，后两项在 $13$ 或 $14$ 相交。若业务采用半开区间 $[start,end)$ ，则 $[9,11)$ 不再冲突；比较式必须从 $\le$ 同步改为 $<$ ，不能只改文案。

删除其中一个 $[10,12]$ 实例只从其归属节点的两张表移除同一 id。若列表按端点值而不保存身份，重复区间会被一并误删。

另一经典结构按 low 建红黑树，并在节点保存子树最大 high。它能最坏 $O(\log n)$ 找到一个相交区间，插删时按局部增强更新 max-high。

要报告全部命中，必须使用相应递归剪枝并单独证明输出敏感界；不能从“一次命中 $O(\log n)$ ”直接推出全部报告 $O(\log n+k)$ 。本页选择 centered 版本，避免把两套节点字段与查询证明混合。

线段树递归分解坐标域或数组索引，一个输入区间可能覆盖多个规范节点，常用于区间聚合和批量更新。Centered interval tree 递归分配区间对象，每个对象归属一个包含其中心的节点，查询输出对象实例。

两者名称都含“区间/segment”，但空间不变量、更新方式和查询接口不同。旋转矩形、二维任意区域与最近邻也不属于一维 interval tree。

参考资料

Herbert Edelsbrunner, Dynamic Data Structures for Orthogonal Intersection Queries, Technical University of Graz, 1980.
Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008.
Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, Section 14.3, for the augmented-BST interval-tree variant.