区间树

跨过中心的区间留在当前节点，其余区间完整落在一侧。查询点相对中心的位置让一个端点约束自动成立，只需按另一端的次序扫描。静态构造还把每个中心与至少一个归属区间绑定：范围查询同时展开两侧时，这个区间正好为节点访问付款。

日程冲突 ​

区间集合为

查询新会议 $[11,14]$ 时，闭区间约定下四项都冲突：$[9,11]$ 在端点 $11$ 接触，另外三项也与查询区间有公共点。若业务采用半开区间 $[start,end)$，则 $[9,11)$ 与 $[14,17)$ 都不和 $[11,14)$ 相交；分组、扫描和交叠判定中的严格性必须一并调整。

若两个会议恰好都有区间 $[10,12]$，结果中仍有两个不同 id。删除一个实例时，只应移除该 id 的两份引用。

固定坐标骨架的动态版本 ​

若可能出现的 $M\ge 1$ 个不同端点坐标预先已知，可先按坐标中位数建立固定中心骨架。高度是 $O(\log (M+1))$，即使当前仅有 $n$ 个活动区间，骨架仍占 $O(M)$ 空间。区间沿中心路径找到唯一归属节点，再插入或删除其两张端点表。

把每张表实现为平衡搜索树公理库平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。，并维护极端元素指针和常数时间逐项前进的链，则一次更新最坏花费 $O(\log (M+1)+\log (n+1))$，总空间 $O(M+n)$。点刺查询仍只有一条路径，故为 $O(\log (M+1)+k)$。这里表的顺序扫描条件很重要，逐项重新搜索后继会增加成本。

范围查询的上述递归在这一版本中需要 $O(V+k)$，其中 $V$ 是访问的骨架节点数。删除可能把节点的归属表清空：若全体区间都已删除，而查询覆盖整个坐标域，递归仍会访问全部 $\mathrm{\Theta }(M)$ 个中心，却输出零项。因此静态版本的“每个展开中心都能向一个输出收费”证明不再适用。要给动态范围报告建立更强的输出敏感界，需要另行设计剪枝、重建或其他索引机制，并证明其维护成本。

与 max-high 增强搜索树的区分 ​

另一经典结构按 low 建红黑树，并在节点保存子树最大 high。它能在最坏 $O(\log (n+1))$ 时间找到一个相交区间，插删时按搜索树增强公理库搜索树增强定理与方法Search-tree augmentation区分可逐层重算的子树摘要与旋转后只需局部修复的中序聚合，并据此维护增强搜索树。更新 max-high。

报告全部命中需要相应的递归剪枝与独立的输出敏感分析公理库输出敏感分析Output-sensitive analysis · Output-sensitive algorithms在明确输出接口后，同时用输入规模与实际输出规模刻画算法运行成本的分析方法。。“找到一个”的界本身没有控制连续搜索、重复访问和全部报告的总成本。中心区间树的两张端点表与 max-high 搜索树的摘要承担不同作用。

与线段树的区分 ​

线段树公理库线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。递归分解坐标域或数组索引，一个输入区间可能覆盖多个规范节点，常用于区间聚合和批量更新。中心区间树递归分配区间对象，每个对象归属一个包含其中心的节点，查询输出对象实例。选型时应先明确要聚合数值、寻找一个命中，还是报告全部实例，再比较相应的空间与更新界。