CODEWITHSUNDEEP
c++algorithmdata-structuresimplementationsegment-tree
William Rookwood
William Rookwood

Reputation: 327

Clear range (set range to zero) lazy segment tree modification

I'd like to add a function to the lazy propagation implementation in the link below that sets a range to 0. There is currently an update_tree function in there which increments a range, but I don't know how to modify it so that it would set a range to zero lazily in O(log(N)) time.

http://se7so.blogspot.com.au/2012/12/segment-trees-and-lazy-propagation.html

I'm thinking of using a "lazy clear" flag on each of the nodes, but how would I know to clear first then lazy add or lazy add then clear (which would be just clear)?

Upvotes: 0

Views: 866

Answers (1)

Justin
Justin

Reputation: 4216

Use a queue instead of a flag on each node which'll contain the operations to process, as long as you use a FIFO data structure you can be sure they are done in the proper order. Unless I am missing the point on the question.

Upvotes: 1

Related Questions