线段树

定义

线段树(Segment Tree)是一种基于分治的二叉树数据结构,每个节点代表一个区间,根代表整个数组范围,叶子代表单个元素,用于高效支持区间聚合查询(和、最值、最大公约数等)与修改。

原理

每个内部节点的区间被平分给左右子树,节点存储其区间的聚合值。单点修改沿根到叶路径更新,区间查询把目标区间分解为 O(log n) 个节点区间合并结果。区间批量修改依赖懒标记(lazy propagation):把待下发的更新暂存于节点,访问子树时再下推,使区间加、区间赋值等操作也保持 O(log n)。空间通常开 4n。

应用

算法竞赛中的区间统计问题、数据库与监控系统的区间聚合、计算几何扫描线(矩形面积并)、可持久化版本(主席树)支持历史版本查询。

对比

树状数组更省空间、常数更小,但功能较窄;线段树通用性强,能维护任意可结合的信息。