Submatrix Sum Queries - GeeksforGeeks

Submatrix Sum Queries - GeeksforGeeks

Given a matrix of size M x N, there are large number of queries to find submatrix sums. Inputs to queries are left top and right bottom indexes of submatrix whose sum is to find out.

How to preprocess the matrix so that submatrix sum queries can be performed in O(1) time.

Example:

tli :  Row number of top left of query submatrix  tlj :  Column number of top left of query submatrix  rbi :  Row number of bottom right of query submatrix  rbj :  Column number of bottom right of query submatrix    Input: mat[M][N] = {{1, 2, 3, 4, 6},                      {5, 3, 8, 1, 2},                      {4, 6, 7, 5, 5},                      {2, 4, 8, 9, 4} };  Query1: tli = 0, tlj = 0, rbi = 1, rbj = 1  Query2: tli = 2, tlj = 2, rbi = 3, rbj = 4  Query3: tli = 1, tlj = 2, rbi = 3, rbj = 3;    Output:  Query1: 11  // Sum between (0, 0) and (1, 1)  Query2: 38  // Sum between (2, 2) and (3, 4)  Query3: 38  // Sum between (1, 2) and (3, 3)  

We strongly recommend you to minimize your browser and try this yourself first.

The idea is to first create an auxiliary matrix aux[M][N] such that aux[i][j] stores sum of elements in submatrix from (0,0) to (i,j). Once aux[][] is constructed, we can compute sum of submatrix between (tli, tlj) and (rbi, rbj) in O(1) time. We need to consider aux[rbi][rbj] and subtract all unncessary elements. Below is complete expression to compute submatrix sum in O(1) time.

Sum between (tli, tlj) and (rbi, rbj) is,     aux[rbi][rbj] - aux[tli-1][rbj] -      aux[rbi][tlj-1] + aux[tli-1][tlj-1]    The submatrix aux[tli-1][tlj-1] is added because    elements of it are subtracted twice.  

Illustration:

mat[M][N] = {{1, 2, 3, 4, 6},               {5, 3, 8, 1, 2},               {4, 6, 7, 5, 5},               {2, 4, 8, 9, 4} };    We first preprocess the matrix and build  following aux[M][N]  aux[M][N] = {1,  3,   6,  10, 16}              {6,  11,  22, 27,  35},              {10, 21,  39, 49,  62},                {12, 27,  53, 72,  89} }    Query : tli = 2, tlj = 2, rbi = 3, rbj = 4            Sum between (2, 2) and (3, 4) = 89 - 35 - 27 + 11                                = 38             

How to build aux[M][N]?
1. Copy first row of mat[][] to aux[][]
2. Do column wise sum of the matrix and store it.
3. Do the row wise sum of updated matrix aux[][] in step 2.

Read full article from Submatrix Sum Queries - GeeksforGeeks