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

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