Range Updates on Segment Trees BUT with different values for each index in the update range.

Revision en1, by redb17, 2017-09-15 04:05:39

Hi, when we have to do range updates on a segment tree from LEFT to RIGHT with a value VAL, we implement this easily because we have to update every INDEX between LEFT and RIGHT by a constant value VAL. My question is -> If we have to update a segment tree from LEFT to RIGHT with values like k, k+1, k+2, k+3,..... k+(RIGHT-LEFT) on INDICES = LEFT, LEFT+1, LEFT+2, LEFT+3,.... RIGHT respectively where 'k' is a random integer provided in the input. How do we do this type of range updates (efficiently of-course) ? MANY THANKS IN ADVANCE.

Tags 2d segment tree, #data structure, advanced data structure, range update, lazy updates, updates, segment trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English redb17 2017-09-15 04:05:39 631 Initial revision (published)