Google OA-10 2024
Problem Description
You are given an array A of N integer elements. You are also given Q queries, where each query is one of the following types:
- 1 i val. Update the value of the element at the i-th index to val i.e. A[i]=val.
- 2 L R: Find the value of function Σi=L, R Σj=i, R [F(i,j)] where F(i,j) represents the sum of elements of array A in index range L to R.
Task: Determine the value of the function for queries of Type 2
Note: Assume 1-based indexing
Input Format:
The first line contains a single integer T, which denotes the number of test cases
For each test case:
The first line contains an integer N
The second line contains an integer Q.
The third line contains N space-separated integers denoting the array A
The next Q lines contain 3 space-separated integers denoting the queries.
Output Format:
For each test case, print the value of the function for queries of type 2 in space-separated format on a new line.
Constraints:
1 <= T <= 10
1 <= N, Q <= 10 ^ 5
1 <= A[i] , val <= 10^3
1 <= i <= N
1 <= L <= R <= N
Example 1:
N = 5
Q = 2
A = [2, 1, 4, 3, 1]
query = [(1, 2, 2), (2, 1, 3)]
Explanation:
The first query is of Type 1. Update A[2] = 2.
Now, array A becomes [2, 2, 4, 3, 1].
The second query is of Type 2 with L = 1, R = 3.
Value of function is equal to F(1,1) + F(1,2) + F(1,3) + F(2,2) + F(2,3) + F(3,3) = 2 + 4 + 8 + 2 + 6 + 4 = 26.
Thus, the answer is 26.
Example 2:
N = 6
Q = 2
A = [2, 1, 3, 4, 6, 1]
query = [(2, 1, 2), (1, 4, 1), (2, 4, 4)]
Sample Output:
6 1