Segment trees doubt

general
, ,
1

void updateLazy(int node, int start, int end, int L, int R){
if(lazy[node] == 1){ //i.e update curr node if lazy has been set previously
ST[node] = (end-start+1) - ST[node];
if(start != end){ //i.e if not a leaf then mark children
lazy[node<<1] = 1-lazy[node<<1];
lazy[(node<<1)+1] = 1-lazy[(node<<1)+1];
}
lazy[node] = 0;
}
if(L > end || R < start) return; // THIS LINE
if(start >= L && end <= R){ //segment inside range hence update
ST[node] = (end-start+1) - ST[node];
if(start != end){ //i.e if no leaf then mark children
lazy[node<<1] = 1-lazy[node<<1];
lazy[(node<<1)+1] = 1-lazy[(node<<1)+1];
}
return; //we donot go down the tree and update every node
}
update(node<<1, start, (start+end)>>1, L, R);
update((node<<1)+1, ((start+end)>>1)+1, end, L, R);
ST[node] = ST[node<<1] + ST[(node<<1)+1];
}

When using lazy update, why do I get wrong answer if I put

if(L > end || R < start) return;

first thing in the function.

If this current range is completely outside our required range, why are we concerned about performing pending updates on it?

2

This is can be understood by considering the following situation.

Let’s take a segment tree node that has two children.
Let the node be denoted by P and its children by C1 and C2.

Now, say we make an update on P. What happens here is:

  1. P gets updated with the desired value.
  2. C1 and C2 get marked for lazy update.

Now, say we make an update on C1. What happens here is:

  1. While moving down to C1 from P, your recursive function will move to C2 also, but it won’t update C2 with its lazy value. It will simply return. It will however, update C1 with its lazy value.
  2. C1 gets updated with the desired value.
  3. Now that the recursive function is done with C1 and C2, it will return back to P. But now P’s value is re-evaluated to be sum of C1 and C2. Here is exactly what goes wrong. C2’s value is not correct. It should have been lazily updated. So now P’s value is wrong because it is being updated with the old value of C2.
3 Likes