2.4.1 线段树与区间树应用

文档摘要

2.4.1 线段树与区间树应用在计算几何的浩瀚星图中，若将点、线、面视作星辰，那么线段树（Segment Tree）与区间树（Interval Tree）就是两座精密校准的天文望远镜——它们不直接观测单个几何对象，却以惊人的时空效率，捕捉空间中动态区间关系的瞬时态、叠加态与交叠态。当你的算法开始频繁回答“哪些线段横跨当前查询区间？”、“给定一条垂直扫描线，它穿过了多少条活动线段？”、“是否存在一对线段在 $x$ 轴上重叠且 $y$ 坐标满足某种约束？”这类问题时，朴素的 $O(n)$ 线性扫描便如烛火照夜，而线段树与区间树，则是打开激光干涉仪级别的空间索引之门。这不是数据结构教科书里被抽象为“区间合并”或“懒标记下传”的静态范式；