Google OA 2024 - Range function
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
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 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.
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