形式陈述

给长度 $n$ 的序列和结合运算 $\circ$ 及单位元，线段树把区间递归二分。每个节点保存其区间的聚合值，父值由两个子值按顺序合并。 建树 $O(n)$，单点更新与区间查询均访问 $O(\log n)$ 个高度或 $O(\log n)$ 个规范区间，空间 $O(n)$。

直觉

任意查询区间可被拆成少量互不重叠的规范二叉区间；预存这些区间的答案即可快速重组。

例子与边界

区间和、最小值、最大子段信息都可通过设计合并规则维护。合并必须结合；非交换运算还必须保持左右顺序。普通线段树不自动支持任意区间更新。

推论与应用

它提供区间查询的统一代数视角，并支撑懒惰传播、持久化和树链分解。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), segment tree.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), segment tree.