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.
Adding Arithmetic progression to range using Segment Tree
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:
Then this code solves the problem implementing the approach explained above.
Can you just briefly explain how you are updating right and left children ? I didn't understand that part. Thanks !
That's so nice thank you!
Do we need to maintain the arrays
K
andD
here?