You are given an array of size n, initially all the values in the array will be 0, and the queries. Each query contains the four values, type of the query T, left point of the range, the right point of a range and a number k, you have to perform the following operations.
If T=0, add the value k to all the integers within the given range (start, end) in the given array,
If T=1, subtract the value k from all the integers within the given range (start, end) in the given array,
Table of Contents
Example
arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}3 4 2 2 -2
Explanation
(0, 2, 4, 1) add 1 to all the integers within the range as it is a type 0 query.
(1, 3, 5, 2) subtract 2 from all the integers within the range as it is a type 1 query.
(0, 1, 4, 3) add 3 to all the integers within the range as it is a type 0 query.
Algorithm to print modified array after multiple queries
- Initialize the array with 0.
- For each query,
- If the type query is to add values, then update the value at the left-1 position by adding the value k and at right position subtract the value k.
- If the type query is to subtract values, then update the value at the left-1 position by subtracting the value k and at right position add the value k.
- Traverse the array and add each previous value to the current value of the array.
- Print the final array.
Explanation
We are given an array, initially, all the values in the array are 0. We are also provided with a q number of the queries, the query will be of two types, each query contains, its type, range, and a number k. If the type of the query is 0, we will add the value k to all of the integers that come within the range. If we are given the type of query as 1, we will subtract the value k from all of the integers, within the range. After executing all the queries, we will be printing that resultant array.
For performing these operations. First we need to check what type of query is given to us. If the query is of first type then we add the value k to the starting point of the range in the array. Also, subtract the value k from the ending point of the range of the array.
We will do the opposite of the previously mentioned technique. If we are given to use type 1 query in which we have to subtract all of the values of integer array within range. Then we will subtract the value k from the starting range value of an array. After that, add the value k at the endpoint index of the range.
For each of the queries given. We have to perform the mentioned technique. Then we will be building an array, in which we will add the previous value to the current value of the array. And store the sum to the current value. Or we can say that we update the current value of the array. After building an array, we will be printing the array. That will be the desired result of a modified array.
Code
C++ code to print modified array after executing the commands of addition and subtraction
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
if (T == 0)
{
arr[left -1] += k;
arr[right] += -k;
}
else
{
arr[left -1] += -k;
arr[right] += k;
}
return;
}
void build(int arr[], int n)
{
for (int i = 1; i < n; ++i)
arr[i] += arr[i-1];
return;
}
int main()
{
int n = 5;
int arr[n+1];
memset(arr, 0, sizeof(arr));
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 0, 2, 4, 1);
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 1, 3, 5, 2);
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 0, 1, 4, 3);
build(arr, n);
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
3 4 2 2 -2
Java code to print modified array after executing the commands of addition and subtraction
import java.util.Arrays;
class AdditionSubtractionQuery
{
static void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
if (T == 0)
{
arr[left -1] += k;
arr[right] += -k;
}
else
{
arr[left -1] += -k;
arr[right] += k;
}
return;
}
static void build(int arr[], int n)
{
for (int i = 1; i < n; ++i)
arr[i] += arr[i-1];
}
public static void main(String arg[])
{
int n = 5;
int arr[] = new int[n+1];
Arrays.fill(arr, 0);
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 0, 2, 4, 1);
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 1, 3, 5, 2);
//query, left, right, k(value which is to add or subtract.
solveQuery(arr, n, 0, 1, 4, 3);
build(arr, n);
for (int i = 0; i < n; ++i)
System.out.print(arr[i]+" ");
}
}
3 4 2 2 -2
Complexity Analysis
Time Complexity
O(q + n) where “q” is the number of queries, and “n” is the number of elements in the array. Because first we perform Q queries which take O(1) time and then building the array requires O(N) time.
Space Complexity
O(n) where “n” is the number of elements in the array. Since we created an array to perform the operations on. The space complexity is linear.