引入
这是由 DengDuck 总结整理的一种处理线段树类问题的算法。
板题引入
给定数列 \(A\{a_i\}\) 和 \(B\{b_i\}\)。
其中有以下操作：
C l r z：\(a_i\leftarrow a_i+z\)，\(i\in [l,r]\)
Q l r：\(\sum\limits_{i=l}^r a_i\times b_i\)
算法概要
先预处理 \(B\) 的前缀和 \(sum_i\)。
对于每一个线段树上的区间的修改实际上就是 \(z\times sum_{[l,r]}\)。
然后懒标记依旧下传 \(z\)，pushdown 操作就同理了。