c - 对超过 2 种类型的查询使用惰性传播

Question

我有很多查询的问题，有四种类型:

1. 添加到范围。

2. 初始化一个范围。

3. 将一个范围与标量相乘。

4. 求一个范围内的运行总和。

由于查询数量巨大，我不得不使用具有惰性传播的线段树，但我一直在研究如何对 2 种以上的查询使用惰性传播。我如何才能确定稍后要进行更新时，将进行什么类型的更新(即加法、乘法、初始化)？

Answer 1

您可以给 Update 函数另一个参数，称之为 Query。根据该参数的值，完成相应的操作。

对于加法和乘法，惰性传播的信息可以包含在两个字段中:

设A为叶子的初始值，有一系列任意的乘法和加法，例如:+u +v *w +x *y +z。在 lazy1 上应用这些操作。所以它的值将是:((u+v) * w +x) * y + z。 lazy2 应该只包含乘法，这将是 w * y。

要更新节点，先乘以 lazy2，然后加上 lazy1。

原因:将操作应用于初始值 A，您将得到:A * w * y + ((u+v)*w +x)*y + z。仅乘法直接影响初始值 A 是微不足道的。因此，这些可以存储在一个字段中，另一个字段可以包含加法，并且还必须对其应用乘法，因为这里的顺序很重要。