### redb17's blog

By redb17, history, 4 years ago,

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

 » 4 years ago, # |   0
 » 4 years ago, # | ← 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#include #define f(i,a,b) for (int i = a; i <= b; i++) using namespace std; const int RIGHT = 131072; const int SIZE = 255005; int N, Q, K[SIZE], D[SIZE], LK[SIZE], LD[SIZE], S[SIZE]; int query(int l, int r, int n = 1, int a = 1, int b = RIGHT) { if(a > r || b < l) return 0; if(a >= l && b <= r) return S[n]; if(LK[n] != 0 || LD[n] != 0) { int sz = (b-a+1) / 2; K[2*n] += LK[n], K[2*n+1] += LK[n] + LD[n]*sz; D[2*n] += LD[n], D[2*n+1] += LD[n]; S[2*n] += LK[n]*sz + LD[n]*sz*(sz-1) / 2; S[2*n+1] += (LK[n] + LD[n]*sz)*sz + LD[n]*sz*(sz-1) / 2; LK[2*n] += LK[n], LK[2*n+1] += LK[n] + LD[n]*sz; LD[2*n] += LD[n], LD[2*n+1] += LD[n]; LK[n] = LD[n] = 0; } int mid = (a+b) / 2; return query(l,r,2*n,a,mid) + query(l,r,2*n+1,mid+1,b); } void update(int l, int r, int k, int d, int n = 1, int a = 1, int b = RIGHT) { if(a >= l && b <= r) { K[n] += k, D[n] += d; LK[n] += k, LD[n] += d; int sz = (b-a+1); S[n] += k*sz + d*sz*(sz-1) / 2; return; } if(LK[n] != 0 || LD[n] != 0) { int sz = (b-a+1) / 2; K[2*n] += LK[n], K[2*n+1] += LK[n] + LD[n]*sz; D[2*n] += LD[n], D[2*n+1] += LD[n]; S[2*n] += LK[n]*sz + LD[n]*sz*(sz-1) / 2; S[2*n+1] += (LK[n] + LD[n]*sz)*sz + LD[n]*sz*(sz-1) / 2; LK[2*n] += LK[n], LK[2*n+1] += LK[n] + LD[n]*sz; LD[2*n] += LD[n], LD[2*n+1] += LD[n]; LK[n] = LD[n] = 0; } int mid = (a+b) / 2; if(l <= mid) update(l,min(mid,r),k,d,2*n,a,mid); if(r > mid) update(max(mid+1,l),r,k + d*max(mid-l+1,0),d,2*n+1,mid+1,b); S[n] = S[2*n] + S[2*n+1]; } int main() { scanf("%d %d", &N, &Q); while(Q--) { int t; scanf("%d", &t); if(t == 1) { int l,r,k,d; scanf("%d %d %d %d", &l, &r, &k, &d); update(l,r,k,d); } else { int l,r; scanf("%d %d", &l, &r); printf("%d\n", query(l,r)); } } } 
•  » » 4 years ago, # ^ |   0 Thanks! @tenshi_kanade @Rezwan.Arefin01
•  » » 3 years ago, # ^ |   0 hello sir, Can you please tell me whether there is a shorter way for updating if there are discontinous values like adding each number in the range to its nearest small multiple of 4 or nearest smallest prime number?
•  » » 3 years ago, # ^ |   0 Can you just briefly explain how you are updating right and left children ? I didn't understand that part. Thanks !
•  » » 2 years ago, # ^ |   +5 That's so nice thank you!
•  » » 2 years ago, # ^ |   0 Do we need to maintain the arrays K and D here?