Related Tags

communitycreator

# How to range update the array using cumulative sum

Farrukh Taqveem

## Problem

Range update means to update the array elements between two indexes (i, j) by adding k (or -k if you want to subtract).

### Brute-force

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$).

### Optimized version

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