Permutacja - Range Query - Part II - Lazy Propagation

Post date: Jan 29, 2013 6:30:25 AM

This post is the sequel to my previous post which explains the problem and proposes a solution. Here we will see how to use the technique of lazy propagation with a segment tree to implement a solution that runs within time limits.

The main problem with the approach in the previous post is that each range update could take

time. What we would like is to have each range update take only time. How do we do this?

Recall how a segment tree works: you have an associative binary operator that you would like to apply to an interval, in our problem this is the minimum operator. The result stored in each node is the minimum in the range that the node represents, or in other words it is the minimum of the values stored in its two children. In the case that a range update is limited to just one of its children, the algorithm only needs to recursively update that child - this is what happens every time when only a single element is updated. However, if the range is contained in both its children then both need to be recursively updated, which ends up being expensive.

For example, consider we update the array

and never about the minimum of , then why should we waste all that effort updating the third element of the segment tree? In fact, adding 1 to every element could just as well be done by incrementing the first element, the minimum of

, by 1, and leaving everything else the same.

Well, of course this is not completely correct, because next we might want to add 1 to only

that's the same size as and holds how much we need to update the children by (where in this problem, an update is adding some integer to every element in the segment).

We can imagine an algorithm that goes something like this:

Let i <- index of current node (so 2i and 2i+1 are children),

    l, r <- the segment the current node is responsible for

    x, y <- the range to update over

    v <- the value to update with (add to array)

Then, to update node i,

    if l==r                  // leaf

       then ST[i] += v

    else if x <= l && r <= y // the range to update completely contains the current range

       then b[i] += v        // don't bother updating children

    else                     // the range cuts

       b[2i] += b[i], b[2i+1] += b[i], b[i] = 0   // We can't be lazy any longer

       update(x, y, v, 2i), update(x, y, v, 2i+1) // Recursively update children

Of course there's still some code needed to handle boundary checking and storing the result in the node.

So, what does this do? If for the current node, it is completely contained in the range we want to update, then we just lazily add to the counter

which says "I'll update children later". But if the range is cut then we need to make sure the children are properly updated, so we push the value in

down.

How does query work then? Very similarly.

Let i <- index of current node (so 2i and 2i+1 are children),

    l, r <- the segment the current node is responsible for

    x, y <- the range to query over

Then, to query from node i,

    if x <= l && r <= y

       then return ST[i] + b[i]

    else

       b[2i] += b[i], b[2i+1] += b[i], b[i] = 0

       return ST[i] = min(query(x, y, 2i), query(x, y, 2i+1))

If the current node is completely contained in the query, we can assume all the children had been increased by , and so just return the minimum plus . Otherwise, we can't be lazy anymore so we update children and take the minimum of the result.

What is the time analysis of this? The analysis of update and query are both the same, and is worst case

. Why? First, imagine if your range touched one edge, for example, it always started at 0. Then, if it is not longer than half of the current node's segment, we only need to recurse to one child. On the other hand, if it is longer than half, then the left child will just be lazy and do little work, so effectively we are still only recursing on one child. Either way, this is

. Now for an arbitrary range, if it is completely contained in one half of the current node's segment, then we only recurse to one child. Otherwise, if it crosses the middle, we recurse on both children, but for each of those recursions the segment touches one edge! Thus the cost is

.

My code for Permutacja can be found here. It contains a few more optimizations and makes sure each update is edge-aligned and gets rid of the query function since we only ever query for the minimum of the whole array.

In my next post in the series I will show how you can do a limited form of range-update range-query with BITs in logarithmic time, which is arguably neater than using lazy propagation with segment trees.

Some practice with lazy propagation:

http://www.spoj.com/problems/LITE/

http://www.spoj.com/problems/HORRIBLE/