Range Sum Query - Mutable

Hard
0/120
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
MicrosoftalibabaNutanix

Problem statement

You are given an array ‘ARR’. You are supposed to process two types of queries - Update an index ‘IND’ with value ‘VAL’ in the array, and find the sum of a range in the array.

You are supposed to implement the class which includes two operations:

1. UPDATE_INDEX(IND, VAL) - It updates the value of ARR[IND] to VAL.
2. SUM\_OF\_RANGE(l, r) - It returns the sum of the subarray ARR[l] to ARR[r] i.e. ARR[l] + ARR[l+1] + ARR[l+1] + ….. + ARR[r-1] + ARR[r].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains integer ‘N’, which denotes the number of elements in the array.

The second line contains ‘N’ integers denoting the elements of the array ‘ARR’.

The third line of each test case contains integer ‘Q’, which denotes the number of queries for the test case.

For each query, the first line contains an integer ‘TYPE_OF_QUERY’.

If ‘TYPE_OF_QUERY’ is equal to 0, the next line contains two integers ‘IND’, and ‘VAL’, which denotes the index to be updated and the value with which the index is to be updated.

If ‘TYPE_OF_QUERY’ is equal to 1, the next line contains two integers ‘l’, and ‘r’, denoting the leftmost element of the sub-array and the rightmost element of the sub-array.
Output Format: 
For each test case, If ‘TYPE_OF_QUERY’ is equal to 1, return  the sum of the given range. Otherwise, update accordingly.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50  
1 <= Q <= 10^4
1 <= N <= 10^4
-10^3 <= ARR[i] <= 10^3
TYPE_OF_QUERY = {0, 1}
0 <= IND <= N
-100 <= VAL <= 100
0 <= l <= r <= N

Time Limit: 1 sec
Sample Input 1:
2
6
1 2 3 4 5 6
3
1
2 5
0
3 5
1
2 5   
5
9 8 7 6 5
3
0
4 13
1
3 4
1
0 4
Sample Output 1:
18
19
19
43
Explanation for Sample Input 1:
In the first test case, The initial array is [1, 2, 3, 4, 5, 6]. In the first query, the sum from index 2 to 5 is 18. In the second query, the third index is updated from 4 to 5. In the third query, the sum from index 2 to 5 is 19.

In the second test case, the given array is [9, 8, 7, 6, 5]. In the first query, index 4 is updated from 5 to 13. In the second query, the sum from index 3 to 4 is 19. In the third query, the sum from index 0 to 4 is 43.
Sample Input 2:
2
4
1 3 5 7 
2
0 1 1 
1 1 3 
3
1 3 5 
2
0 1 1 
1 1 2
Sample Output 2:
13
6
Hint

Can you traverse over the given subarray and find the sum, etc accordingly?

Approaches (3)
Brute Force

The idea is to iterate through each subarray to find the sum.

For the update query, simply update the value at the given index.

For the sum query, iterate through the given subarray and add all the given indices.

 

The steps are as follows:

Update(‘IND’, ‘VAL’):

  • Make the ‘IND’ index of the array ‘ARR’ equal to ‘VAL’.

SUM_OF_RANGE(‘l’, ‘r’):

  • Initialize an integer sum equal to 0.
  • Iterate from ‘i’ = ‘l’ to ‘r’:
    • Add the value of ARR[i] to ‘SUM’.
  • Return the integer ‘SUM’.
Time Complexity

O(N*Q), where ‘N’ is the number of elements in the array and ‘Q’ is the number of queries.

 

For the update query, the time complexity is O(1).

For the sum query we are iterating through the subarray hence, the time complexity is O(N) for each sum query.

Hence the overall time complexity for all the queries is O(N*Q).

Space Complexity

O(1) 

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Range Sum Query - Mutable
Full screen
Console