11 篇的线段树每次改变一个叶子，再更新祖先。若给一整段元素加5，逐点更新会把许多共同祖先反复访问。可以直接修改覆盖整段的节点摘要，把尚未传播到孩子的操作保存在节点上；只有查询或更新需要进入孩子时，才继续传播。

延迟执行不是跳过执行。摘要必须立即反映当前逻辑值，标记必须足以恢复孩子未来应该看到的状态。只支持加法时，两个标记相加即可；加入赋值以后，复合顺序就成为正确性条件。

让两种更新共享一个表达式

输入整数数组，长度n，沿用11的0基半开区间。add(l,r,d)把区间每项增加d，assign(l,r,v)把每项改成v，sum(l,r)返回区间和；0≤l≤r≤n，空区间更新不产生作用，空和为0，非法区间抛IndexError。

把作用于单个元素的更新表示为仿射函数f(x)=ax+b。区间加d为(1,d)，区间赋值v为(0,v)，无操作为(1,0)。本篇a只需0或1；这种表示的目的不是引入任意线性代数接口，而是让两种操作共享可推导的复合规则。

节点摘要是(sum,len)。整段应用(a,b)后，新摘要为

(sum,len)\mapsto(a\,sum+b\,len,len).

必须保存或能由区间边界得到len：仅知道旧和，不能判断加d后的新和。长度不同的全零区间都有旧和0，却分别增加不同总量。这是摘要不足的反例。

先旧后新，不能交换

设孩子尚未执行的旧操作为g(x)=aₒx+bₒ，新操作为f(x)=aₙx+bₙ。真正的时间顺序是先g后f，因此合成标记为

f(g(x))=(a_n a_o)x+(a_n b_o+b_n).

旧操作	新操作	合成结果
加d₁	加d₂	加d₁+d₂
赋值v	加d	赋值v+d
加d	赋值v	赋值v
赋值v₁	赋值v₂	赋值v₂

例如先赋值5再加2，每项应为7；先加2再赋值5，每项应为5。若两种顺序得到相同结果，至少一种复合逻辑不正确。把“没有赋值标记”编码成0也会出错，因为赋值0是一个合法且会覆盖旧值的操作；本实现用恒等对(1,0)，与赋值0的(0,0)区分。

复合满足结合律，因为函数复合满足结合律，但不满足交换律。多次完整覆盖同一节点时，可以只保留复合后的一个标记，仍要保留时间次序。AtCoder官方接口用 composition(new,old) 返回new∘old，本篇采用相同方向。

摘要何时可信

根的sum始终反映全局当前值。沿访问路径先下传全部祖先标记后，当前节点的sum才反映其区间当前逻辑值；尚未接收祖先标记的后代摘要允许陈旧。本节点标记表示“已经计入本节点sum，但尚未计入孩子”的操作。查询到达一个被完整覆盖的节点时，祖先标记已经沿路径下传，可以直接返回sum，不必继续推到叶子。

部分覆盖时先push：把父标记依次作用到两个孩子的sum，并以先孩子旧标记、后父标记的顺序复合；最后把父标记重置为恒等。父操作发生在孩子已有状态之后，所以此时的方向仍是new∘old。下探完成后pull，用两个孩子的最新sum重算父sum。

完整覆盖: apply(node, tag) -> 改sum + 合成tag
部分覆盖: push(node) -> 递归到相交孩子 -> pull(node)
完整查询: 直接读sum
部分查询: push(node) -> 查询相交孩子 -> 相加

正确性可以按操作序列归纳。初始树由叶子建立，所有标记恒等。apply的摘要公式逐元素求和成立，标记复合保持时间顺序；push只把已经发生的逻辑更新换一种存储方式，数组逻辑值不变；pull由两段互不相交区间求和成立。每次递归区间严格缩短，因此终止。

查询可能push并修改内部表示，但不改变逻辑数组。本实现是可变树；这些写操作不能直接照搬到14篇的共享历史节点上。版本树若共享节点，就必须另行设计复制边界，本篇没有实现持久化lazy。

对数界依赖标记可合成

区间更新和查询在每层至多留下两个部分覆盖的边界，完全覆盖节点立即停止。高度O(log(n+1))，每个访问节点的apply、push和pull只做常数次算术，因此两种操作最坏O(log(n+1))，构造O(n)，逻辑空间O(n)，递归栈O(log(n+1))。空树作为单独常数边界处理。

这个分析要求摘要更新和标记复合为常数成本。若某种操作不能从现有摘要计算新摘要，就不能仅仅“加一个标记”而照搬复杂度。例如要求区间每项取绝对值，仅凭sum和len无法确定结果：[-1,1]与[0,0]都有和0、长2，取绝对值后的和却分别为2和0。需要更多状态或另一种算法。

本篇是确定性最坏操作数界，不是摊还分析。Python整数位长随数值增长时，乘加不再是任意规模下的常数时间；这里只使用a=0/1，仍须考虑b乘区间长度与累计和的位复杂度。

测试要让标记真正相遇

运行 python3 examples/advanced-algorithms/check_lazy_sum.py。本次109872组小数组与双更新组合、seed20260919的3000次随机更新均通过；实际反例结果为先赋值5后加2得到7，相反次序得到5，赋值0后的局部查询为0。结果保存于 examples/advanced-algorithms/results/lazy_sum.json，配套标记检查卡说明复合方向。这些是有限差分结果，不是对全部序列的证明。仅做完整区间更新后立即查询完整区间，会一直读取根sum，可能没有触发错误的push。更有效的序列是先完整赋值，再局部加法，再分别查询单点和跨边界区间，让新旧标记在不同层相遇。

独立参照逐项修改列表，比较全部小区间和。赋值0、负加法、部分重叠、空区间、长度非2次幂分别覆盖不同边界，不能被一个随机大数组的总和检查替代。

练习

从 [1,2,3,4] 开始，依次assign(0,4,5)、add(1,3,2)、assign(2,4,0)。手算最终数组和sum(1,4)，列出一次push前后的父子标记。
故意把复合公式写成old∘new，找一个最短操作序列，使完整区间sum暂时正确、某个局部查询错误。解释为何必须检查局部查询才能暴露问题。

参考资料

AtCoder Lazy Segment Tree官方文档：映射族封闭性、composition方向及practice2_k仿射例子。官方例子使用模整数；本文采用普通整数，数值模型不同。