Skip to main content

Google

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. 1 i val. Update the value of the element at the i-th index to val i.e. A[i]=val.
  2. 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