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?

Question

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?

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

Answer 1

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

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

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

If we do this twice:

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. Multiply by a
2. Subtract a
3. Add 1

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.

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).

Answer 2

Yes, it is indeed possible, at least in some cases.

Basically, you need a way to efficiently store the lazy operation, and a way to efficiently combine two stored lazy operations into one.

For instance, say the update operation is segment assignment, that is, a[l] = x, a[l+1] = x, ..., a[r-1] = x, a[r] = x. This operation on the whole subtree can be stored as just the value x, which will mean that the operation was to assign x to every vertex of this subtree. For lazy propagation in vertex v, we just apply it to immediate children of vertex v, and store the same lazy operation x there. Note that any old lazy operation in children is just erased by the assignment. Such is the nature of assignment.

---

As for your added example, operation arr[i] = (1 - (1 - arr[i]) * a), let us see how the value changes after two such operations with constants a and b.

Before operations, let the value be v.

After the first one, it becomes w = 1 - (1 - v) * a, which is a*v + (1-a)*1.

After the second operation, the value becomes 1 - (1 - w) * b, which is b*w + (1-b)*1, which in turn is b*a*v + b*(1-a)*1 + (1-b)*1, and finally becomes (b*a)*v + (1-b*a)*1. (I may have mixed up +s and -s, but that hopefully does not change the whole picture.)

We can now see that the value is a linear function of the original value, so we can store the coefficients b*a and 1-b*a of the linear and constant terms, respectively.

The problem now is that the coefficients may grow too quickly, and will soon exceed the capacity of the storage type (int, double or whatever). Now, if the problem deals with integer residues modulo some integer instead of just integers or reals, that's not an issue; otherwise, storing the coefficients soon becomes problematic.