Find initial array from given array after range sum query in C++

In this problem, we get an array res[] of size N. Our task is to find initial array from given array after range sum query.

We need to find the starting array on which the array rel[] will be returned when executing a [s, e, val] query.

The solution for each [s, e, val] query is

s -> starting index

e -> ending index

val -> Update the value to be added to each element from s to e in the array.

Input : rel[] = {7, 4, 8}
Query[][] = {{1, 2, 1},
{0, 1, 3}}
Output : {4, 0, 7}

Explanation The translation of −

Explanation −

initialArray = {4, 0, 7}; query = {1, 2, 1}; finalArray = {4, 1, 8}
initialArray = {4, 1, 8}; query = {0, 1, 3}; finalArray = {7, 4, 8}

Solution

The simple way to solve the problem is to iterate through all queries, solve them the same way we solved the problem for all queries, and then return the found array at the end. Here, in order to find the initial array, we need to operate it in the opposite way, i.e. subtract it from the given array.

Example

Program example to illustrate how our solution works

#include <iostream>
using namespace std;
void calcInitialArrayQueries(int arr[], int n, int query[][3], int q) {
   for (int i = 0; i < q; i++) {
      for (int j = query[i][0];j <= query[i][1]; j++) {
         arr[j] = arr[j] - query[i][2];
      }
   }
   for (int i = 0; i < n; i++)
      cout<<arr[i]<<" ";
}
int main() {
   int arr[] = { 5, 1, 8, 2, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   int query[][3] = { {0, 2, -2}, {1, 4, 3}};
   int q = sizeof(query) / sizeof(query[0]);
   cout<<"Initial array : "; calcInitialArrayQueries(arr, n, query, q);
   return 0;
}

Output

Initial array : 7 0 7 -1 6

The above is the detailed content of Find initial array from given array after range sum query in C++. For more information, please follow other related articles on the PHP Chinese website!