Trusted answers to developer questions
Trusted Answers to Developer Questions

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)O(N). For N, the time complexity of the algorithm would be O(N2N^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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring