You are not logged in. Please login at www.codechef.com to post your questions!

×

Need Help in Lazy Propogation!

Hello Codechef Users!

I need Help in Lazy Propogation. I have clearly understood segment-trees.

Please anyone instead of posting Links as an answer, if you can explain, it will be very helpful!

Thanks in Advance :)

asked 01 Aug '15, 21:59

bradley's gravatar image

3★bradley
6562321
accept rate: 20%


Basic Idea how lazy progation works is given below.

Taken from - http://www.spoj.com/forum/viewtopic.php?f=27&t=8296

Lazy Propagation means that you only update what you actually need to, when you need to.

For example, if we have a segment tree that covers the range 1-20. If we update segment [1,20], we update only the value of the root node of the tree and set a flag on it's children [1,10] and [11,20] to let them know that they need to be updated.

Next, if we query [6,7] then when we reach a node in the traversal that has the update flag on, we need to flag it's children and update it's value.

[1,10] is flagged for update query [6,7] Traversal Route: [1,10] - push update flag to [1,5] and [6,10] and update value of [1,10] [6,10] - push update flag to [6,8] and [9,10] and update value of [6,10] [6.8] - push update flag to [6,7] and [8,8] and update value of [6,8] [6,7] - push update flag to [6,6] and [7,7] and update value of [6,7]

This leaves [1,5], [6,6], [7,7], [8,8], [9,10] flagged for update.

Its easy to understand if you just try it on a paper.

For its program - just google it you will get.

Hope it helps - Happy Coding!!

link

answered 01 Aug '15, 22:43

adi28galaxyak's gravatar image

5★adi28galaxyak
1164
accept rate: 14%

Yes Brother! I clearly understood what I really need to do! Thanks a lot! :)

(02 Aug '15, 10:54) bradley3★

hello bradley:

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 it would help you.

if you have any doubt then you may ask :)

link

answered 01 Aug '15, 23:10

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×699
×156

question asked: 01 Aug '15, 21:59

question was seen: 775 times

last updated: 02 Aug '15, 10:54