Блог пользователя redb17

Range Updates on Segment Trees BUT with different values for each index in the update range.
Автор redb17, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Adding Arithmetic progression to range using Segment Tree

→ Ответить
»
7 лет назад, # |
← Rev. 7   Проголосовать: нравится +11 Проголосовать: не нравится

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
→ Ответить