core · 线段树

线段树：把区间递归二分成一棵树

线段树 (segment tree) 的想法直白：把整段 $[0, n-1]$ 不断对半切, 每个节点缓存自己负责那一段的聚合值（和 / 最小 / 最大 / gcd…）。查询任意 [l, r] 时，能整段命中的节点直接拿现成值，沾边的才往下拆，一次只碰 $O(\log n)$ 个节点。

每个节点管区间 [lo, hi]。查询 query([l,r]) 从根往下，对每个节点三选一：
完全不相交（hi<l 或 lo>r）→ 这棵子树剪掉，返回幺元；
[l,r] 完全盖住 [lo,hi] → 直接采用 node.val，不再深入；
部分重叠 → 拆成左右孩子递归，再把结果 combine 起来。
拖 l / r、点单步，看树上节点按三态黄（采用）/ 浅黄（递归）/ 灰（剪掉）点亮。

1 · 为什么最多只碰 O(log n) 个节点？

关键在「整段命中就停」。可以证明：在每一层，真正被拆开（部分重叠）的节点最多 2 个—— 左边界一个、右边界一个，中间的整块区间全部被「直接采用」。树高 $O(\log n)$ ，每层 ≤ 4 个相关节点 → 总共 $O(\log n)$ 。这正是它比「逐个累加」快的根源：能整片处理就绝不拆到底。

2 · 线段树 vs 树状数组

BIT 更短更快、常数更小，但基本只擅长可减的聚合（和、异或）。线段树更通用: min / max / gcd / 区间赋值 / 区间最大子段和 这些「不可减」的聚合它都能装，代价是 ~4n 空间和更长的代码。需要区间整体修改时，还能加懒标记，见 lazy propagation 一页。

3 · 实际应用

竞赛里几乎是区间问题的通用结构。工程中：扫描线求矩形面积并 / 重叠（EDA 芯片版图 DRC 检查、GIS 地图图层叠加、网页布局碰撞，配合离散化与 lazy）、 行情 / 监控的区间最值与统计、区间染色 / 赋值、可持久化线段树（主席树，查历史版本 / 区间第 k 小，数据库 MVCC 式快照）、游戏与图形里的区间碰撞 / LOD。