如何实现支持区间加法与区间求和的懒标记线段树？
题干与适用场景
给定长度为 n 的整数数组，在线处理两种操作：把闭区间 [l, r] 的每个元素加上 delta，查询 [l, r] 的总和。要求初始化 O(n)，每次更新和查询 O(log n)，允许 O(n) 额外空间。先确认下标是闭区间、delta 可为负数，以及是否需要持久化版本。
面试官考察点
强回答会先写节点不变量：tree[p] 始终是该节点覆盖区间的真实总和，lazy[p] 表示尚未写入子节点、但已经计入 tree[p] 的统一增量。候选人应能解释完整覆盖只更新当前节点、部分覆盖先 push，再递归，并把增量乘以区间长度。
回答前需要澄清的问题
- 更新是加法、赋值还是取最大值？不同操作的 lazy 合并律不同，不能套用同一标记。
- 查询是和、最小值还是最大值？节点聚合与标记应用公式会改变。
- 区间是否闭合？下面采用闭区间
[l, r]；若使用半开区间，分裂和长度都要统一。 - 数值范围多大？
tree[p] + delta * length可能溢出 32 位整数，应选择足够宽的类型。
推荐解法与推导
用数组存储一棵隐式二叉树。节点 [lo, hi] 的中点为 mid，左右子区间分别是 [lo, mid] 和 [mid+1, hi]。对完整覆盖的更新，把 delta * (hi-lo+1) 加到 tree[p]，并把 delta 累积到 lazy[p]；对子节点的真实值暂不修改。
class LazySumTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * max(1, self.n))
self.lazy = [0] * len(self.tree)
if self.n:
self._build(1, 0, self.n - 1, values)
def _build(self, p, lo, hi, a):
if lo == hi:
self.tree[p] = a[lo]
return
mid = (lo + hi) // 2
self._build(p * 2, lo, mid, a)
self._build(p * 2 + 1, mid + 1, hi, a)
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
def _apply(self, p, lo, hi, delta):
self.tree[p] += delta * (hi - lo + 1)
self.lazy[p] += delta
def _push(self, p, lo, hi):
if self.lazy[p] == 0 or lo == hi:
return
mid = (lo + hi) // 2
d = self.lazy[p]
self._apply(p * 2, lo, mid, d)
self._apply(p * 2 + 1, mid + 1, hi, d)
self.lazy[p] = 0
def add(self, ql, qr, delta):
if not self.n or ql < 0 or qr >= self.n or ql > qr:
raise ValueError("invalid range")
self._add(1, 0, self.n - 1, ql, qr, delta)
def _add(self, p, lo, hi, ql, qr, d):
if ql <= lo and hi <= qr:
self._apply(p, lo, hi, d); return
self._push(p, lo, hi)
mid = (lo + hi) // 2
if ql <= mid: self._add(p * 2, lo, mid, ql, qr, d)
if qr > mid: self._add(p * 2 + 1, mid + 1, hi, ql, qr, d)
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
def total(self, ql, qr):
if not self.n or ql < 0 or qr >= self.n or ql > qr:
raise ValueError("invalid range")
return self._sum(1, 0, self.n - 1, ql, qr)
def _sum(self, p, lo, hi, ql, qr):
if ql <= lo and hi <= qr: return self.tree[p]
self._push(p, lo, hi)
mid = (lo + hi) // 2
ans = 0
if ql <= mid: ans += self._sum(p * 2, lo, mid, ql, qr)
if qr > mid: ans += self._sum(p * 2 + 1, mid + 1, hi, ql, qr)
return ans每层最多访问常数个边界节点，更新和查询均为 O(log n)；树和标记数组使用 O(n) 空间。正确性关键是 apply 同时更新总和与待传播增量，push 传播后清零，父节点在子调用返回后重新合并。
替代方案与取舍
只有点更新和前缀和时，Fenwick 树代码更短、常数更小；只有离线区间加法且最后统一读取时，差分数组更简单。懒标记线段树适合在线、区间更新与区间聚合同时存在的场景，但实现复杂度更高。若更新是区间赋值，需要额外的“是否有赋值标记”并规定赋值覆盖旧加法的顺序。
失败场景、边界与反例
- 忘记乘以区间长度，
[2, 5]加 3 只增加 3 而不是 12。 - 完整覆盖后直接递归到子节点，失去 lazy 的收益并可能重复应用增量。
- push 后没有清零，下一次访问会重复加同一个标记。
- 父节点在部分更新后不重新合并，后续完整覆盖查询会返回旧总和。
- 混用闭区间与半开区间，导致单元素区间或
mid+1越界；入口应统一校验空数组、l > r和n=0。
测试与验证清单
用朴素数组作为 oracle，随机生成更新和查询并逐步比较；覆盖单元素、全数组、左右边界、负增量、重复覆盖和全相同值。额外断言每次递归返回后父节点等于两个子节点之和，并对大数组检查整数类型不会溢出。若实现迭代版，增加跨层 push 的等价性测试。
追问与延伸
如何支持区间赋值和区间加法同时存在？
为每个节点维护可选赋值标记与加法标记。新赋值覆盖旧赋值和旧加法；新加法累积到已有赋值之后。push 时先下发赋值，再下发加法，顺序是正确性的核心。
如何支持区间最小值？
把 tree[p] 改为区间最小值；区间加法对最小值只需加 delta，因此 lazy 仍可累积。若加入区间取最小或取最大，标记不再是简单加法，需要 segment tree beats 等更复杂不变量。
如何获得历史版本？
采用持久化线段树，对更新路径复制节点、共享未修改子树；每次更新约复制 O(log n) 个节点，根指针代表一个版本，空间从一次性的 O(n) 变为随更新次数增长。