如果更新比简单的加法或乘法更复杂，那么如何应用惰性方法来更新段树？ [英] How is it possible to apply the lazy approach to update a segment tree if the update is more complex than simple addition or multiplication?

问题描述

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

Consider this question. In this segment tree solution, we are updating all nodes of the tree in the given range. Is it possible to apply lazy propagation to this problem?

编辑：考虑在每次更新操作中， arr [i] =（1-（1-arr [i]）* a），其中 L< = i< = R 和 a 是一个常数。

Consider that in every update operation arr[i] = (1-(1-arr[i])*a), where L<=i<=R and a is a constant.

推荐答案

我假设您的查询操作正在找到 [L，R] 。

I'll assume your query operation is finding the sum in a range [L, R].

您当然想高效地执行此操作，可能每次操作 O（log n）。

You certainly want to do this efficiently, probably in O(log n) per operation.

您需要一种将数据存储在 lazy 字段中的方法，该方法可让您在遍历树时计算更新

You need a way to store data in the lazy field that allows you to compute the updates when traversing the tree for a query.

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

Let's see if we can write the update in a nicer way:

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

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

Which is equivalent to (applied to an entire range):

1. 乘以 a


2. 减去 a


3. 添加 1

1. Multiply by a
2. Subtract a
3. Add 1

更新惰性字段时，很明显，您只是增加了<$ c的指数$ c> a 。

When updating the lazy field, it's clear that you just increase the exponent of a.

您可以按照链接到的惰性传播文章中的描述，懒惰地完成这三个步骤。

You can do all of these 3 lazily as described in the lazy propagation article you link to.

因此，您的更新操作可以分为3个惰性更新，每个惰性更新在 O（log n）时间内完成的 O（log n）。

So your update operation can be split into 3 lazy updates, each done in O(log n) time, for a total time of O(log n).

这篇关于如果更新比简单的加法或乘法更复杂，那么如何应用惰性方法来更新段树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！