Lazy propagation range update

156 views Asked by At

I was reading lazy propagation on GFG and it says following for range update

For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node Segment Tree Diagram

I don't understand if the range is 2 to 5 why are we supposed to update only 27 and not other nodes which also contain index = 2 in their ranges

Link to the article

1

There are 1 answers

1
williamBMDK On

Firstly, could you provide a link to the article.

With lazy propagation you would have to update the node with value 3 and the node with value 27 to process the update query in range [2, 5]. However, you only implicitly update the subtree of the node with value 27, by updating the lazy value of the node with value 27. I assume the text just doesn't mention the node with value 2, but from what you have provided the updates of nodes which contains index 2 are not explicitly excluded.