Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

community creator

Submatrix Sum Queries

Yash Kumar

This is a competitive programming style question, so let’s define the problem statement with sample input-output and input constraints.

Problem statement

Given a N×MN \times M matrix consisting of integers, answer QQ queries on the matrix of type (x1,y1,x2,y2)(x1, y1, x2, y2); i.e., sum the elements in the submatrix with top left corner (x1,y1)(x1, y1) and bottom right corner (x2,y2)(x2, y2).

Input format

The first line of input consists of two space-separated integers, NN and MM (1N,M1000)(1 \leq N,M \leq 1000).

The next NN lines contain M space-separated integers that each represent the matrix.

The next line contains a single integer QQ that represents the number of queries (1Q106)(1 \leq Q \leq 10^6).

The next QQ lines contain four space-separated integers x1,y1,x2,y2x1,y1,x2,y2, respecitvely(1x1,x2N,1y1,y2M)(1 \leq x1,x2 \leq N, 1 \leq y1,y2 \leq M).

Output format

For each x1,y1,x2,y2x1,y1,x2,y2, print a single integer, i.e., the sum of the sub-matrix as described in the problem.


Sample

Input

5 5
1 4 7 3 2
3 4 2 5 9
6 1 6 2 1
2 5 8 7 6
3 6 9 8 3
2
2 2 3 5
3 2 5 4

Output

30
52

Explanation

For query 11 -> x1=2,y1=2,x2=3,y2=5x1=2, y1=2, x2=3, y2=5, the corresponding submatrix is:

1362344156726893527829163

The sum of the elements is:

4+2+5+9+1+6+2+1=304 + 2 + 5 + 9 + 1 + 6 + 2 + 1 = 30


Brute force

Pretty straightforward. For each query, loop over the submatrix and calculate the sum.

Each query will be answered in O(NM)O(N*M). The time complexity of the solution will be O(QNM)O(Q*N*M).

With given constraints on NN and MM, we can answer a handful of queries in a few seconds, but definitely not a million queries.

The code for brute force is:

input.txt
5 5
1 4 7 3 2
3 4 2 5 9
6 1 6 2 1
2 5 8 7 6
3 6 9 8 3
2
2 2 3 5
3 2 5 4

Optimization

We can extend the concept of prefix sums in 1-D arrays to 2 dimensions.

Quick recap. The prefix sum in the 1-D array AA is defined as:

pref[i]=k=1iA[k]pref[i] = \sum_{k=1}^iA[k]

Then, the sum of a subarray A[i...j]A[i...j] is pref[j]pref[i1]pref[j] - pref[i-1].

Let’s define the prefix sum in 2-D, say pref[i][j]pref[i][j] is the sum of elements of the submatrix with top left corner as (1,1)(1,1) and bottom right corner as (i,j)(i,j), or pref[i][j]=k=1il=1jA[k][l]pref[i][j] = \sum_{k=1}^i\sum_{l=1}^jA[k][l].

1362344156726893527829163
pref[2][3] = A[1][1] + A[1][2] + A[1][3] + A[2][1] + A[2][2] + A[2][3]

Let’s see how we can use the prefix sum matrix to get the sum of any submatrix in O(1)O(1) time:

sum(x1,y1,x2,y2)=pref[x2][y2]pref[x2][y11]pref[x11][y2]+pref[x11][y11]sum(x1, y1, x2, y2) = pref[x2][y2] - pref[x2][y1- 1] - pref[x1-1][y2] + pref[x1-1][y1-1]

The illustration below will help you to visualize the formula:

Let's count how many time each cell is counted in the formula
1 of 10

Pre-computation

Each query can be answered in O(1)O(1) if we have the pref[]pref[] array.

The pref[]pref[] array can be computed in O(NM)O(N*M) in a similar way as above. Here is the formula:

pref[i][j]=pref[i][j1]+pref[i1][j]pref[i1][j1]+A[i][j]pref[i][j] = pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1] + A[i][j]

If we iterate the matrix from left to right and top to bottom, at (i,j)(i,j) we would already have the values at (i1,j1),(i1,j)(i-1,j-1), (i-1,j), and (i,j1)(i,j-1). So, calculating the value of pref[i][j]pref[i][j] is a constant time operation, i.e., O(1)O(1).

Pre-computing the entire pref[][]pref[][] matrix takes O(NM)O(N*M) time.


Answering queries

By using pref[][]pref[][], we can answer each query in O(1)O(1).

Thus, the total time complexity is, O(NM+Q)O(N*M +Q).


Code

main.cpp
input.txt
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>

using namespace std;

int main() {
  ifstream cin("input.txt");

  int N, M, Q;
  cin >> N >> M;
  int A[N][M];
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      cin >> A[i][j];
  cin >> Q;

  int pref[N][M];
  for (int i = 0; i < N ; i++){
    for (int j = 0; j < M; j++) {
      pref[i][j] = A[i][j];
      if (i > 0) pref[i][j] += pref[i-1][j];
      if (j > 0) pref[i][j] += pref[i][j-1];
      if (i > 0 && j > 0) pref[i][j] -= pref[i-1][j-1];
    }
  }

  while (Q--) {
    int x1, y1, x2, y2 ;
    cin >> x1 >> y1 >> x2 >> y2;
    x1 --; y1--; x2--; y2--;

    int sum = pref[x2][y2];
    if (y1 > 0) sum -= pref[x2][y1-1];
    if (x1 > 0) sum -= pref[x1-1][y2];
    if (x1 > 0 and y1 > 0) sum += pref[x1-1][y1-1];
    
    cout << sum << "\n";
  }

  return 0;
}

RELATED TAGS

community creator
RELATED COURSES

View all Courses

Keep Exploring