线段树Segment tree

递归划分下标区间，为每个区间维护聚合值。

常见操作#

n 为数组长度；合并函数满足结合律且单次 $O(1)$ 。

操作	时间复杂度	条件与说明
从数组构建	$O(n)$	自底向上合并节点。
读取单点	普通版 $O(1)$ ；懒标记版 $O(\log n)$	普通数组布局可直接读叶子；含未下推懒标记时须先沿路径下推，不能直接读取旧叶值。
单点更新	$O(\log n)$	更新到根路径上的聚合值。
区间聚合查询	$O(\log n)$	例如区间和、最小值；合并函数成本非 $O(1)$ 时需相乘。
区间更新	$O(\log n)$	需要匹配操作的懒标记及可正确合并的作用函数；普通线段树不自动具有该保证。

表示固定下标范围。动态开点、持久化和二维线段树有不同空间界。

基础原理参考资料

AtCoder Library · Segtree构建、单点更新、区间聚合的接口和代价。

AtCoder Library · Lazy Segtree支持区间作用所需的代数约束和复杂度。