lazy propogation explanation required

general
,
1

I was searching the explanation of lazy propogation and I find this ->

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)

We updated the node of range 9…15 bcoz it completely falls inside the range 5…15 .
My doubt->
Suppose if no further query comes for the range 9…15 , than how will be update each of the child node of the parent node (9…15) …??

2

hello va1ts7_100:

first thing about lazy propagation is that you do not need to update any child node unless such type of query/update occur(when node is not completely inside query/update range) that’s why it is fast because in case of query control always take value from parent node if it is completely inside query range. in case of update if parent is completely inside update range then OK modification will be on parent node and lazy value passes to its children if parent is not completely inside update range then control goes to children of that node and if child is completely inside range then child will be updated and lazy value passes to its children. If next time these children/child node is not completely inside query/update range then control will go inside these children/child node and now again check children of current node is completely inside range or not if yes then update and pass lazy value to its children if not then control again go inside and so on. Means explanation in one line WHEN YOU NEED THEN UPDATE i hope you have got clear your doubt.

here i am not explaining lazy propagation just trying to clear doubt. for learning lazy propagation there are various sources GO AND LEARN its FUN

3 Likes
3

@admin123 , u really cleared one of my doubt… thanks a lot :slight_smile: .

4

See if no query comes for range 9 to 15 then there is no need of updating its children…and if a query comes which contains at least one [9 15] then the node will be updated and lazy values will pass to its children. Think what happens if after marking 9…15 as y the range update or query is like 14 to 17 ?..this will help you.

5

thanks @apptica… i got that point now :slight_smile: