How do I apply range updates in a segment tree?

But now let's say the original array elements are updated from 1 to 3. Now array elements are 3 6 2 4 5. Now the same query is requested again. So I have to rebuild the whole persistence bucket tree.

If updating a range involves changing every item in the range in an asymmetric manner, then the best option is to apply a singleton update for every item in the specified range. This will be O(range_sz * log n)

, where n

is the number of items in the tree.

I'm assuming you know how to perform a singleton update in O(log n)

if you don't ask.

If your update is more limited, such as "set all items in the range to a given value v

", you can use lazy updates: for every node in the segment tree whose associated range is included in the update range, set some custom field to a value v

. Then, when requested, whenever you accept a node's range (if its range is included in the request range), set that field and, if it matters, take that value as min / max

or whatever you are asking for.

This will support both updates and requests for O(log n)

.