Lazy update on Segment tree

Question

Im having a problem which need a structure that can handle 2 operations:

1. Change values of nodes from position x to position y to newValue.

2. Get the sum of values from position a to b.

The number of nodes is 50000 and number of queries is 50000. Im trying to implement IT tree with lazy update but i can't figure out how. The first operation is somehow different from the usual add and multiply operation.

Answer 1

For a given node of range [l...r] store the sum of the range and the lazy value of the corresponding range. Build the segment tree using the initial values with lazy value = -1.

For update operation proceed with the segment tree with the normal approach. At a particular node, update the sum of the node using the lazy value, and update the lazy value of the child nodes. When the range completely overlaps with the node, update the value of sum for that node and update the lazy of he child nodes with the current value.

For query operation proceed with the segment tree with the normal approach. At a particular node, update the sum of the node using the lazy value, and update the lazy value of the child nodes. Then if the range overlaps with the node, return the sum value of that node.