DK 树

· · 算法·理论

推荐在 cnblogs 上阅读

引入

这是由 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 操作就同理了。