Matrix Range Query Mutable

Easy

0/40

Average time to solve is 15m

Contributed by

2 upvotes

Asked in company

Problem statement

You are given a N * M matrix GRID. You are also given Q queries. Your task is to Perform two types of query-

1) Find the sum of the rectangular submatrix defined by the upper left corner and lower right corner for each query. The position of the upper left and lower right corner is given.

2) Change the value of the element at a given position. Position and the new value of the cell are given. 

All indexes are 0 based.

For example:

GRID =[ [1, 2, 3],
        [4, 5, 6],
        [7, 8, 0] ]
Q = 2
Update element at (3,3) to 9 
left corner = (1, 1), right corner = (2, 2)
submatrix=[ [5, 6],
            [8, 9] ]   
Answer = 28

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, ‘Q’ denoting the number of rows and number of columns in GRID and the number of queries. 

Then ‘N’ lines follow. Each of the next 'N' lines contains ‘M’ space-separated integers denoting the elements of the matrix GRID.

Then ‘Q’ lines follow. Each of the lines contains the type of the query and the query.

If the TYPE = 1, then it contains four space-separated integers ‘X1’, ‘Y1’, ‘X2’, ‘Y2’ where (‘X1’, ‘Y1’) is an upper left corner. (‘X2’, ‘Y2’) is the lower right corner.

If the TYPE = 2 then it contains two space-separated integers ‘X’ ‘Y’, and a NEW_VALUE to be stored at a given position.

Output Format:

For each query of TYPE=1 print the sum of elements in the submatrix defined by the upper left and lower right corner.

The output of each test case is printed on a different line.

Note:

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, M <= 1000 
1 <= Q <= 10 ^ 5
-10^4 <= GRID[i] <= 10^4

‘Q’ is the number of queries.
‘N’, ‘M’, GRID[i] is the number of rows, number of columns and cell value of GRID.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

12 7
4

Explanation of Sample Input 1:

For the first test case, the first query submatrix is [[7, 5]]
After second query array becomes= [2, 5, 3, 2]
For third query submatrix is [[2, 5]]
For the second test case, first query submatrix is [[1, 1], [1, 1]]

Sample Input 2:

Sample Output 2:

0 0
0

Hint 1

Hint 2

For each query calculate the sum by brute force.

Approaches (2)

Approach 1

Approach 2

Brute force

We will iterate over the subgrid and calculate the sum of all elements in this subgrid of each query. And for the update, we will update the table directly.

Algorithm:

For each query
1. IF TYPE = 2
  1. grid[X][Y]=new_value
2. ELSE
  1. SUM=0
  2. For ROW in X1 to X2
    1. For COLUMN in Y1 to Y2
      1. SUM+=grid[ROW][COLUMN]
  3. Print (SUM)

Time Complexity

O(Q * N * M) where ‘N’, ‘M’, ‘Q’ are the number of rows, number of columns and number of queries respectively.

For each query, we will iterate over the subgrid defined by the top left corner and lower right corner.

Space Complexity

O(1),

Constant space is used.

(100% EXP penalty)

Matrix Range Query Mutable

Console