本文主要是介绍DK 树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
推荐在 cnblogs 上阅读
引入
这是由 DengDuck 总结整理的一种处理线段树类问题的算法。
板题引入
给定数列 A { a i } A\{a_i\} A{ai} 和 B { b i } B\{b_i\} B{bi}。
其中有以下操作：
C l r z： a i ← a i + z a_i\leftarrow a_i+z ai←ai+z， i ∈ [ l , r ] i\in [l,r] i∈[l,r]
Q l r： ∑ i = l r a i × b i \sum\limits_{i=l}^r a_i\times b_i i=l∑rai×bi
算法概要
先预处理 B B B 的前缀和 s u m i sum_i sumi。
对于每一个线段树上的区间的修改实际上就是 z × s u m [ l , r ] z\times sum_{[l,r]} z×sum[l,r]。
然后懒标记依旧下传 z z z，pushdown 操作就同理了。
这篇关于DK 树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
