线段树 Segment Tree

数据结构 · 每个节点管一段区间，存这段的聚合

什么是线段树

要反复求「数组某一段的和（或最值）」，逐个累加是 O(n)，区间一长就慢。线段树把数组建成一棵二叉树：每个节点管一段区间、存这段的聚合值（这里用和）。根管整个数组，往下对半分，叶子是单个元素——父节点的和正好是左右孩子之和。

这里给 8 个数 [2, 5, 1, 4, 9, 3, 7, 6] 建了一棵求和线段树（共 15 个节点，根的和是 37）。填两个下标 a、b：点「区间和」看它怎么把一段拆成几个「现成的整段」相加；点「更新」把第 a 个元素改成 b，看改一个数只牵动一条叶→根的路径。

区间查询的诀窍：把目标区间拆成 O(log n) 个「正好被某个节点完整覆盖」的整段，直接取它们存好的和，不必逐个累加。单点更新也只动叶子到根的一条路径，同样 O(log n)。要做区间整体修改（比如把一段都加 5），还能配「懒标记」把更新延迟下推、批量处理。

另有一个更省空间的同类结构——树状数组（Fenwick / BIT），用一维数组 + lowbit 巧算前缀和，代码更短更省内存，但不如线段树直观、也没这么通用（线段树能装和、最值、最大子段和等各种聚合）。

线段树在哪里用

它把「树 + 数组聚合」用到了极致——也是这趟结构之旅里很硬核的一站。