Constant time range add operation on an array

Hello Everyone,

Given an array of size N which is initialized with all zeros. We are given many ranges add queries, which should be applied to this array. We need to print the final updated array as our result.

Examples:

N = 6 Arr = [0, 0, 0, 0, 0, 0] rangeUpdate1 [0, 2], add 100 Arr = [100, 100, 100, 0, 0, 0] rangeUpdate1 [1, 5], add 100 Arr = [100, 200, 200, 100, 100, 100] rangeUpdate1 [2, 3], add 100 Arr = [100, 200, 300, 200, 100, 100] Which is the final updated array.

We can process each query in constant time using this logic when a query to add V is given in range [a, b] we will add V to arr[a] and –V to arr[b+1] now if we want to get the actual values of the array we will convert the above array into prefix sum array.

See below example to understand:

Arr = [0, 0, 0, 0, 0, 0]

rangeUpdate1 [0, 2], add 100
Arr = [100, 0, 0, -100, 0, 0]

rangeUpdate1 [1, 5], add 100.
Arr = [100, 100, 0, -100, 0, 0]
Note: You can not add -100 at 6th index because array length is 6.

rangeUpdate1 [2, 3], add 100
Arr = [100, 100, 100, -100, -100, 0]

Now we will convert above operation array to prefix sum array as shown below,
Arr = [100, 200, 300, 200, 100, 100]

Which is the final updated array.
So in effect, when we add a value V to specific index of the array, It represents adding V to all elements right to this index, that is why we add –V after range to remove its effect after its range of add query.

// C++ program to get updated array after many array range

// add operation

#include <bits/stdc++.h>

using namespace std;

// Utility method to add value val, to range [lo, hi]

void add( int arr[], int N, int lo, int hi, int val)

{

arr[lo] += val;

if (hi != N - 1)

arr[hi + 1] -= val;

}

// Utility method to get actual array from operation array

void updateArray( int arr[], int N)

{

// convert array into prefix sum array

for ( int i = 1; i < N; i++)

arr[i] += arr[i - 1];

}

// method to print final updated array

void printArr( int arr[], int N)

{

updateArray(arr, N);

for ( int i = 0; i < N; i++)

cout << arr[i] << " " ;

cout << endl;

}

// Driver code

int main()

{

int N = 6;

int arr[N] = {0};

// Range add Queries

add(arr, N, 0, 2, 100);

add(arr, N, 1, 5, 100);

add(arr, N, 2, 3, 100);

printArr(arr, N);

return 0;

}

Output

100 200 300 200 100 100