3

考虑这个问题。在这个分段树解决方案中，我们正在更新给定范围内的树的所有节点。是否可以对这个问题应用惰性传播？

编辑：考虑在每个更新操作arr[i] = (1-(1-arr[i])*a)中， whereL<=i<=R和a是一个常数。

4

2 回答 2

3

我假设您的查询操作是在一个范围内找到总和[L, R]。

您当然希望有效地执行此操作，可能在O(log n)每次操作中。

您需要一种将数据存储在lazy字段中的方法，该方法允许您在遍历树进行查询时计算更新。

让我们看看我们是否可以以更好的方式编写更新：

v = 1 - (1 - v) * a
  = 1 - (a - av)
  = 1 - a + av

如果我们这样做两次：

1 - a + av = 1 - (1 - [1 - a + av]) * a
           =  1 - (a - a + a**2 - a**2 v)
           = 1 - a + a - a**2 + a**2 v
           = 1 - a**2 + a**2 v

这相当于（应用于整个范围）：

  1. 乘以a
  2. 减去a
  3. 添加1

更新惰性字段时，很明显您只需增加a.

您可以按照链接到的惰性传播文章中的描述惰性地执行所有这 3 项操作。

因此，您的更新操作可以拆分为 3 个惰性更新，每个都O(log n)及时完成，总时间为O(log n).

于 2018-04-13T20:39:28.493 回答
2

是的，这确实是可能的，至少在某些情况下是这样。

基本上，您需要一种有效存储惰性操作的方法，以及一种有效地将两个存储的惰性操作合并为一个的方法。

例如，假设更新操作是段赋值，即, a[l] = x, a[l+1] = x, ..., 。对整个子树的这个操作可以只存储为 value ，这意味着该操作将分配给这个子树的每个顶点。对于 vertex 中的惰性传播，我们只需将其应用于 vertex 的直接子代，并在那里存储相同的惰性操作。请注意，孩子中任何旧的惰性操作都会被赋值删除。这就是任务的性质。a[r-1] = xa[r] = xxxvvx

至于您添加的示例 operation arr[i] = (1 - (1 - arr[i]) * a)，让我们看看在使用常量a和进行两次此类操作后值如何变化b。

运算前，设值为v。

在第一个之后，它变为w = 1 - (1 - v) * a，即a*v + (1-a)*1。

第二次操作后，值变为1 - (1 - w) * b，即b*w + (1-b)*1，依次为b*a*v + b*(1-a)*1 + (1-b)*1，最后变为(b*a)*v + (1-b*a)*1。（我可能混淆了 +s 和 -s，但希望这不会改变整体情况。）

我们现在可以看到该值是原始值的线性函数，因此我们可以分别存储线性项和常数项的b*a系数1-b*a。

现在的问题是系数可能增长得太快，很快就会超过存储类型（或其他）的int容量double。现在，如果问题涉及整数余数模某个整数而不是整数或实数，那不是问题；否则，存储系数很快就会出现问题。

于 2018-04-13T20:26:57.247 回答