Lazy propagation in segment tree?

Question

Well, I was trying to solve this Flipping coins problem on Codechef. Am solving it with segment trees. But getting time limit exceed. I searched and found that I have to use lazy propagation. But I am unable to understand. My update function works recursively(top to bottom). Please give some hints or explain it with example. Also point out where I have to change the code.

In flipping coins, during update if a node value is 1 change it to 0 and if it is 0 change it to 1.

start and end are limits of original array. tree is segment tree array.

void update(int node, int start, int end,int pos)//pos=position to update
{
    if(start==end) tree[node]=(tree[node]==0) ? 1 : 0;
    else
    {
        int mid=(start+end)/2;
        if(mid>=pos) update(2*node + 1, start, mid, pos);
        else update(2*node + 2, mid+1, end, pos);

        tree[node]=tree[2*node +1] + tree[2*node +2];
    }
}

Answer 1

To mark only 5..15 as "yes", below is all you need. Only 7 nodes are involved in the operation, much less than what if you don't use lazy propagation. It can be proved that at most 2logn - 1 nodes may be involved, where n is the range.

         0..31u
         /    \
      0..15u 16..31n
      /    \
   0..8u  9..15y
   /   \
0..4n  5..8y 

(u: unknown, look deeper; y: yes; n: no)

Without lazy propagation, segment tree isn't any better than plain array.

More details for how to implement is left to you. You should work it out by yourself.

Answer 2

Lazy propagation means updating only when required. Its a technique that allows range updates to be carried out with asymptotic time complexity O(logN) (N here is the range).

Say you want to update the range [0,15] then you update the nodes [0,15] and set a flag in the node that says that it's children nodes are to be updated (use a sentinel value in case the flag is not used) .

Possible Stress Test Case :

0 1 100000

0 1 100000

0 1 100000 ...repeat Q times (where Q = 99999) and the 100000th Query would be

1 1 100000

In that case most implentations would sit flipping 100000 coins 99999 times just to answer one simple query in the end and time out.

With Lazy propagation you just need to flip the node [0,100000] 99999 times and set/unset a flag that its children are to be updated. When the actual query itself is asked, you start traversing its children and start flipping them, push the flag down and unset the parent's flag.

Oh and be sure you are using proper I/O routines (scanf and printf instead of cin and cout if its c++) Hope this has given you an idea of what lazy propagation means. More information : http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296

Answer 3

I will contrast lazy update operation to a normal update operation and how this changes query operation.

In a normal single update operation you update the root of a tree and then recursively update only the needed part of the tree (thus giving you a O(log(n)) speed). If you will try to use the same logic for a range updates, you can see how it can deteriorate to O(n) (consider very broad ranges and see that you will mostly need to update both parts of the tree).

So in order to overcome this O(n) idea is to update the tree only when you really need it (query/update on the segment which was previously updated, thus making your updates lazy). So here is how it works:

• creation of a tree stays absolutely the same. The only minor difference is that you also create an array which holds information about potential updates.
• when you update the node of the tree, you also check whether it needs to be updated (from the previous update operation) and if it is - you update it, mark children to be updated in the future and unmark the node (being lazy)
• when you query the tree, you also check whether the node needs to be updated and if so update it, mark it's children and unmark it afterwards.

Here is an example of update and query (solving maximum range query). For a full code - check this article.

void update_tree(int node, int a, int b, int i, int j, int value) {
    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
        return;

    if(a >= i && b <= j) { // Segment is fully within range
        tree[node] += value;
        if(a != b) { // Not leaf node
            lazy[node*2] += value;
            lazy[node*2+1] += value;
        }
        return;
    }

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}

and query:

int query_tree(int node, int a, int b, int i, int j) {
    if(a > b || a > j || b < i) return -inf; // Out of range

    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];

    return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j));
}