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