How to range update the array using cumulative sum

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

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved