区间合并与最大子段和
在线段树与 lazy propagation 两页中，节点只缓存一个数（和 / 最小 /
最大）。但节点也能缓存一组互相关联的量，前提是能定义「左孩子的信息加右孩子的信息得到父节点的信息」这条合并规则，且该规则满足结合律、并有一个幺元——否则不同的树形切分会给出不同答案，查询时也没有可返回的空值。 经典例子是最大子段和 (maximum subarray
sum)：数组里有正有负，问某段 [l, r] 内连续一截的和最大能到多少。它没法只靠一个数往上合—— 跨越中点的那截会被切成两半，单看一侧无法得知另一侧的信息。
注 · 每个节点存四个量，跨中点的情况才拼得回来：sum 是整段总和，pre 是从左端起的最大前缀和，suf 是到右端止的最大后缀和，best 是段内任意位置的最大子段和。合并左右孩子
、
时 best 有三个候选——只在左的 L.best、只在右的 R.best、以及跨越中点的 L.suf + R.pre（左的最大后缀接右的最大前缀），取最大即可。第三项正是区间合并存在的理由。
1 · 为什么合并顺序不能乱
注 · combine 不满足交换律：L.suf + R.pre 假定
在
的左边、且两截挨着。实测反例很小——两个叶子 3 与
按左右顺序合并得 pre = 3、suf = 1，交换后变成 pre = 1、suf = 3。但它满足结合律（2000 组随机验证无反例），所以建树时按兄弟合并、查询时按命中的连续段合并，用的可以是同一个 combine；查询
时被完整盖住的若干极大节点本就从左到右首尾相接（
全枚举验证严格平铺），严格按这个次序累积，跨节点边界的子段才接得上。
2 · 实际应用
这类「节点存复合信息 + 自定义合并」的线段树，是竞赛区间题（SPOJ GSS 系列、最大子段和带单点修改）的标配。 工程里同源的思路：区间统计聚合（一段时间窗里的最大连续增长 / 最长连续可用资源）、 磁盘 / 内存的最大连续空闲块查找（合并相邻空闲区间维护「最长连续 0」）、 文本编辑器里区间属性的快速汇总。凡是「答案可能横跨子区间边界、需要边界信息才能拼」的场景，都落在这套框架里。