redb17's blog

Range Updates on Segment Trees BUT with different values for each index in the update range.
By redb17, history, 7 years ago, In English

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.

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Adding Arithmetic progression to range using Segment Tree

→ Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it +11 Vote: I do not like it

It certainly depends on the update you wish to perform. For that case you mention, you update nodes with an arithmetic progression. I'd do it by maintaining three values for each node, K[i] = first term of progression, D[i] = difference between consecutive terms of progression and S[i] = current sum of node. Then to update the sum for a certain node i of size sz with a progression of first value k and difference d, we would add . The update to first terms and differences is a simple addition. We only need to be careful about updating the first term when moving to the right in updates that cover multiple ranges. Lazy updates work in the same way.

Consider a problem with two types of queries:

  • 1 l r k d = update range [l, r] with an arithmetic progression of first term k and difference d.
  • 2 l r = report sum of all elements in range [l, r].

Then this code solves the problem implementing the approach explained above.

C++ Code
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you just briefly explain how you are updating right and left children ? I didn't understand that part. Thanks !

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That's so nice thank you!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do we need to maintain the arrays K and D here?

    → Reply