core · 线段树

线段树与区间的递归二分

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

注 · 查询时每个节点三选一。设节点管区间 $[lo, hi]$ ：与 $[l, r]$ 完全不相交时剪掉这棵子树、返回幺元；被 $[l, r]$ 完全盖住时直接采用 node.val、不再深入；部分重叠时拆成左右孩子递归，再把结果 combine 起来。

图 0-1 · 查询路径上节点的三态着色：黄为采用、浅黄为递归、灰为剪掉。可拖动

l

与

r

并单步执行。

1 · 访问节点数的上界

注 · 关键在「整段命中就停」。在每一层，真正被拆开（部分重叠）的节点最多 2 个——左边界一个、右边界一个，中间的整块区间全部被直接采用。树高 $O(\log n)$ ，每层相关节点不超过 4 个，总共 $O(\log n)$ 。实测 $n = 1 \dots 40$ 的全部 $(l, r)$ ，逐层的 partial 数确实不超过 2、访问数不超过 4，上界在 $n = 4$ 、 $[1, 2]$ 处取到。

2 · 与树状数组的分工

注 · BIT 更短更快、常数更小，但它靠前缀相减取区间，要求聚合可逆（构成群），因而基本只擅长和与异或这类聚合。线段树只要求 combine 满足结合律并有幺元（构成 monoid），不要求可逆、也不要求交换——min、max、gcd、区间赋值、区间最大子段和这些都能装进去，区间合并那页正是靠不交换的 combine 吃饭。代价是更长的代码与更多的节点：本页引擎按「每个内部节点恰有两个孩子」建树，节点数恒为 $2n-1$ （实测 $n = 8$ 得 15、 $n = 34$ 得 67、 $n = 100$ 得 199）；工程上常见的 4n 是堆式下标数组为避免越界而开的长度，不是节点数。需要区间整体修改时再加懒标记，见 lazy propagation 一页。

3 · 实际应用

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