Last Updated: 2 Apr, 2021

Matrix Range Query Mutable

Easy

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

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

Solve now

Approaches

01 Approach

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)

Solve now

02 Approach

We will use a two-dimensional Fenwick tree to support individual updates and computing some over a prefix. FenwickTree[a][b] will store the sum of submatrix starting at (a’, b’) and ending at (a, b). Here a’ = a&(a+1) , and b’ = b&(b+1).

E.g. go from the Least significant bit and reset the last continuous set bits.

To calculate the sum we will iterate over all the submatrices which in addition give us the required prefix matrix.

To add value we will consider all the submatrixes which have the current position in their Fenwick tree.

Algorithm:

We initially initialize the Fenwicktree[N][M].
For R in range(N)
1. For C in range(M)
  1. Add this element to the 2-D Fenwick tree
For each query
1. If TYPE==1
  1. Use the sum method of the Fenwick tree to calculate the prefix sum of (X2, Y2), (X2, Y2 - 1), (X1 - 1, Y2), (X1 - 1, Y1 - 1)
  2. Print (FenwickTree.sum(X2, Y2) - FenwickTree.sum(X2,Y1 - 1) - FenwickTree.sum(X1 - 1, Y2) + FenwickTree.sum(X1 - 1, Y1 -1))
2. ELSE
  1. Delta = NEW_VALUE - GRID[R][C]
  2. Delta is the amount by which we want to increase the value
  3. We will update the Fenwick tree by increasing all submatrixes in the Fenwick tree containing this position.
  4. FenwickTree.add(X, Y, NEW_VALUE - GRID[R][C])
sum(x, y)
1. This function calculates the prefix sum
2. Iterate over all the sub rows
  1. Iterate over all the sub-columns
    1. Result += sum of sub rows and subcolumn matrix
    2. Column = column &(column+1)-1
  2. row= row &(row+1)-1
3. Return result
add(x, y,delta)
1. This function is to update the Fenwick tree
2. For all the super rows
3. For all the super column
4. Fenwicktree[row][col]+=delta

Solve now