线段树

扫描线算法是计算几何中最优雅的算法范式之一。它的核心思想简单得令人惊讶：用一条假想的线扫过整个平面，只在关键点停下来处理。这个朴素的想法却催生了计算复杂度理论的重大突破。1976年，Michael Shamos 和 Dan Hoey 发表了标志性的线段相交检测算法，证明了扫描线结合平衡二叉树可以在 $O(N \log N)$ 时间内判断 $N$ 条线段是否存在交点——这在当时是革命性的结果。随后，Bentley 和 Ottmann 将其扩展为报告所有交点的算法，Fortune 在 1986 年用扫描线构造 Voronoi 图，这些工作奠定了计算几何作为独立学科的基础。 ...

假设你正在开发一个实时数据分析平台，需要频繁执行两类操作：查询某个时间段内的数据总和，以及更新某个时间点的数值。如果用普通数组，查询需要 $O(n)$ 时间遍历整个区间；如果用前缀和数组，查询确实降到了 $O(1)$，但每次更新又需要 $O(n)$ 时间重新计算前缀。当数据量达到百万级别、操作频率达到每秒数千次时，这两种方案都无法满足性能要求。 ...