Arithmetic Progression Queries

Ninja
0/200
Average time to solve is 44m
29 upvotes
Asked in companies
SprinklrOptumOYO

Problem statement

Given an integer array(ARR) of size N, the following operations need to be performed:

update(l, r, val) : Add (val + i) to arr[l + i] where, 0 <= i <= r - l.

rangeSum(l, r): return the sum of all elements in the array from index l to r, i.e., the sum of array arr[l...r].

Two type of queries denote these operations:

Type 1: for update(l, r, val) operation.
Type 2: for rangeSum(l, r) operation.

Note: (1 based indexing) for the queries.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains two space-separated integers N and Q, denoting the size of the input array and the number of operations to be performed, respectively.

The next Q lines contain operations, one per line. Each operation starts with an integer which represents the type of operation. 

If it is 1, then it is of the first type and is followed by three single space-separated integers l, r, val(in this order). 

If it is 2, it is of the second type and is followed by two single space-separated integers l r(in this order). The meanings of l, r, and val are well explained in the statement.
Output Format: 
For each operation of type 2, print an integer on the single line - the sum of the arr[l..r].

Output for each test case will be printed in a separate line.
Note 
You are not required to print anything, and it has already been taken care of. Just implement the function.
Constraints: 
1 <= N <= 10^5
1 <= Q <= 10^5
1 <= l <= r <= N
0 <= val <= 10^6
0 <= arr[i] <= 10^6

where 'N' is the size of the array, 'Q' is the number of queries, and arr[i] denotes the ith element of the array.

Time Limit: 1 sec.
Sample Input 1:
4 4
1 1 1 0
2 1 4
1 4 4 1
2 3 4
2 1 2
Sample Output 1:
3
2
2
Explanation For Sample Output 1:
In the first query, we have to calculate the sum of elements between indexes 1 and 4. So, the output will be 1 + 1 + 1 + 0 = 3. 

In the second query, we have to increment the element at index 4 with value 1. So the array will be 1, 1, 1, 1.

In the third query, we have to calculate the sum of elements between indexes 3 and 4. So, the output will be 1 + 1 = 2.

 In the fourth query, we have to calculate the sum of elements between indexes 1 and 2. So, the output will be 1 + 1 = 2.
Sample Input 2:
5 4
1 2 2 3 3
1 1 3 2
2 1 5
1 1 3 1
2 3 5
Sample Output 2:
20
15
Hint

Iterate over the array to perform both update and range sum operations.

Approaches (3)
Brute Force

In this approach, for each operation, we will be simply doing what we need to do to perform that task. For update operation, we will iterate over the array and update the given value in increasing order as mentioned in the problem description update operation. Similarly, for rangesum operation, we will iterate over the array for the given range and add all elements. For example, consider the input array as [1,2,3,4,5,6] and two operations to be performed.

  1. update(3,6, 2) - for this we will iterate through the array from index 3 to 6(considering 1 based indexing) and update the values as arr[3] = arr[3] + 2, arr[4] = arr[4] + 3, arr[5] = arr[5] + 4, arr[6] = arr[6] + 6., where arr in the array.
  2. rangesum(2,4) - for this we will iterate through the array from index 2 to 4 and add the corresponding values to our result and return the final result. So res = arr[2]+arr[3]+arr[4].
Time Complexity

O(N), per operation - where N is the size of the input array.

 

In the worst case, for each operation, we will be iterating over the array once.

Space Complexity

O(1).

 

In the worst case, we will be using constant extra space(we will not count the additional array used to convert the given input values to long type).

Code Solution
(100% EXP penalty)
Arithmetic Progression Queries
Full screen
Console