Trusted answers to developer questions

Farrukh Taqveem

**Range update** means to update the array elements between two indexes `(i, j)`

by adding `k`

(or `-k`

if you want to subtract).

Let’s see a simple brute-force example:

#include <iostream> using namespace std; const int SIZE = 10; void rangeUpdate(int* arr, int i, int j, int k){ while(i<=j){ arr[i] += k; i++; } } int main() { int arr[SIZE] = {0,0,0,0,0,0,0,0,0,0}; rangeUpdate(arr, 2, 5, 10); // O(N) rangeUpdate(arr, 4, 7, 20); // O(N) for(int i = 0; i < SIZE ; i++) cout << arr[i] <<" "; return 0; } // O(updates * N) or O(N^2) if updates = N

Take a single update `i -> j with k`

, with the time complexity $O(N)$.
For N, the time complexity of the algorithm would be O($N^2$).

We can optimize this algorithm using the cumulative sum technique.
A **cumulative sum array** is one whose value at each index is the sum of all previous indexes plus itself (e.g., `[1,2,3,4]`

becomes `[1,3,6,10]`

).
While doing multiple range updates, all we need is to put start & end identifiers in the array for each update and, at the end, sum them all together.

Given an array [0,0,0,0,0]
for query1 => `1 -> 3 add 10`

we would simply add 10 at index 1 and add -10 at index 3+1 = 4.

The array would look like `[0, 10, 0, 0, -10]`

. A cumulative sum on this array would result in `[0, 10, 10, 10, 0]`

, which is exactly what we wanted. The cumulative step will be done once each query is run.

#include <iostream> using namespace std; const int SIZE = 10; void rangeUpdate(int* arr, int i, int j, int k){ arr[i] += k; arr[j+1] -= k; } void cumulativeSum(int* arr){ for(int i = 1; i < SIZE ; i++) arr[i] += arr[i - 1]; } int main() { int arr[SIZE] = {0,0,0,0,0,0,0,0,0,0}; rangeUpdate(arr, 2, 5, 10); // O(1) rangeUpdate(arr, 4, 7, 20); // O(1) cumulativeSum(arr); for(int i = 0; i < SIZE ; i++) cout << arr[i] <<" "; return 0; } // O(N) even if updates = N

RELATED TAGS

communitycreator

CONTRIBUTOR

Farrukh Taqveem

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses