怎样理解又乘又加的线段树懒标记

大凡两个标记,无非是先乘再加,与先加再乘的区别罢了。

先加再乘

我们以 (val) 来表示这个结点原始的值,(add)(mul) 顾名思义是两个标记。这样,这个结点的值就被更新成了 ((val+add) imes mul)。(其实 (add) 还要跟区间长度搞一搞,这里就省略了)。我们就知道,这个结点经历了加 (add) 和乘 (mul) 之后的值是 ((val+add) imes mul)

现在,从他的父亲那里传来一组标记 ((\_add,\_mul))。本着先加后乘的原则,这个结点的值变成了 (((val+add) imes mul + \_add) imes \_mul) 也就是 ((val + add + \_add / mul) imes mul imes \_mul),这就相当于原始是 (val) 的值加上了一组标记 ((add + \_add / mul , mul imes \_mul))。出现了小数,这样不好。

先乘再加

有了上面的分析经验我们可以轻易的推算出 (val) 打上((mul,add)) 变成 (val imes mul + add)。再来一组标记 ((\_mul,\_add))就变成了 ((val imes mul + add) imes \_mul + \_add) 也就是 (val imes mul imes \_mul + (add imes \_mul + \_add)),就相当于原始是 (val) 的值加上了一组标记 ((mul imes \_mul,add imes \_mul + \_add))。十分正常,这样好。

因此,我们就能轻松地写出先乘再加的标记打法了。

原文地址:https://www.cnblogs.com/poorpool/p/8469201.html