Saturday, 23 Oct 2021

# Print modified array after performing queries to add (i – L + 1) to each element present in the range [L, R]

Print modified array after performing queries to add (i – L + 1) to each element present in the range [L, R]
Given an array arr[] consisting of N 0s (1-based indexing) and another array query[], with each row of the form {L, R}, the task for each query (L, R) is to add a value of (i – L + 1) over the range [L, R] and print the array arr[] obtained after performing all the queries.
Examples:

Input: arr[] = {0, 0, 0}, query[][] = {{1, 3}, {2, 3}}Output: 1 3 5Explanation: Initially the array is {0, 0, 0}.Query 1: Range of indices involved: [1, 3]. The value (i – 1 + 1) for each index i in the range is {1, 2, 3}. Adding these values modifies the array to {1, 2, 3}.Query 2: Range of indices involved: [2, 3]. The value (i – 2 + 1) for each index i in the range is {0, 1, 2}. Adding these values modifies the array to {1, 3, 5}.Therefore, the modified array is {1, 3, 5}.
Input: arr[] = {0, 0, 0, 0, 0, 0, 0}, query[][] = {{1, 7}, {3, 6}, {4, 5}}Output: 1 2 4 7 10 10 7

Naive Approach: The simplest approach to solve the given problem is to traverse the given array over the range [L, R] and add the value (i  –  L  +  1) to each element in the range for every query. After completing all the queries, print the modified array obtained arr[].Below is the implementation of the above approach:

C++

#include
using namespace std;

void updateQuery(vector queries,
int N)
{

vector a(N + 1, 0);

int n = N + 1;

int q = queries.size();

for (int i = 0; i < q; i++) {                     int l = queries[i];                     int r = queries[i];                              for (int j = l; j