Last Updated: 6 Sep, 2020
Arithmetic Progression Queries
Ninja
Asked in companies
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.
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.
Approaches
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.
- 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.
- 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].
In this approach, we will maintain a prefix sum array prefixSum where prefixSum[i] will denote the sum of array elements from index 1 to i(1-based indexing). 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 and also update the prefixSum array accordingly. For rangesum(l, r) operation, we just need to return prefixSum[r] - prefixSum[l - 1].
For example, consider the input array as [1,2,3,4,5,6] and two operations to be performed.
- 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 given array values will become equals to [1,2,5,7,9,11] and prefix array will now looks like this - [1,3,8,15,24,35].
rangesum(2,4) - return
prefixSum
[4] -
prefixSum
[1] i.e 15 - 1 = 14.
The data structure we will use is Segment Tree with Lazy Propagation which is a quiet, efficient approach for doing for range updates. Our segment tree will store the sum of all segments of the array efficiently. Now,
For rangesum(l, r) operation, we will be performing the sum-query operation of the segment tree, which receives l and r as parameters where l denotes the left bound, and r denotes the right bound of the segment for which the sum is to be calculated.
For update(l, r, val) operation, as this is a range update operation so for this, we will use lazy-propagation: an advanced version of segment trees. We will build a lazy tree of type Pair containing two values ‘a’ and ‘d’, where ‘a’ denotes the first value of the series we need to update with, and ‘d’ denotes the common difference of the series. While updating each node in the segment tree, we will directly calculate the sum of the A.P series using the formula,
Sn = n2*(2 * a + (n - 1) * d),
Where n is the number of terms that need to be updated, so n equals the size of the segment for which the node is holding its sum (root node of the segment tree will hold the sum of the whole array, so its size equals the size of the array).
Similar problems