Data Structure & Algorithms
Arrays Two Dimensional
Sub Matrix Sum Queries

# Sub-matrix Sum Queries

## Problem Description

Given a matrix of integers A of size N x M and multiple queries Q, for each query, find and return the submatrix sum.

Inputs to queries are top left (b, c) and bottom right (d, e) indexes of submatrix whose sum is to find out.

NOTE:

• Rows are numbered from top to bottom, and columns are numbered from left to right.
• The sum may be large, so return the answer mod 109 + 7.
• Also, select the data type carefully, if you want to store the addition of some elements.
• Indexing given in B, C, D, and E arrays is 1-based.
• Top Left 0-based index = (B[i] - 1, C[i] - 1)
• Bottom Right 0-based index = (D[i] - 1, E[i] - 1)

### Problem Constraints

``````1 <= N, M <= 1000
-100000 <= A[i] <= 100000
1 <= Q <= 100000
1 <= B[i] <= D[i] <= N
1 <= C[i] <= E[i] <= M``````

### Input Format

``````The first argument given is the integer matrix A.
The second argument given is the integer array B.
The third argument given is the integer array C.
The fourth argument given is the integer array D.
The fifth argument given is the integer array E.
(B[i], C[i]) represents the top left corner of the i'th query.
(D[i], E[i]) represents the bottom right corner of the i'th query.``````

### Output Format

``Return an integer array containing the submatrix sum for each query.``

### Example Input

``````Input 1:
A = [   [1, 2, 3]
[4, 5, 6]
[7, 8, 9]   ]
B = [1, 2]
C = [1, 2]
D = [2, 3]
E = [2, 3]

Input 2:
A = [   [5, 17, 100, 11]
[0, 0,  2,   8]    ]
B = [1, 1]
C = [1, 4]
D = [2, 2]
E = [2, 4]
``````

### Example Output

``````Output 1:
[12, 28]

Output 2:
[22, 19]
``````

### Example Explanation

``````Explanation 1:
For query 1: Submatrix contains elements: 1, 2, 4 and 5. So, their sum is 12.
For query 2: Submatrix contains elements: 5, 6, 8 and 9. So, their sum is 28.

Explanation 2:
For query 1: Submatrix contains elements: 5, 17, 0 and 0. So, their sum is 22.
For query 2: Submatrix contains elements: 11 and 8. So, their sum is 19.``````

### Output

Java
``````public class Solution {
public int[] solve(int[][] A, int[] B, int[] C, int[] D, int[] E) {
int MOD = 1000000007;
int n = A.length;
int m = A[0].length;
int q = B.length;

int[][] prefixSum = new int[n][m];

// Calculate prefix sum for rows
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prefixSum[i][j] = A[i][j];
if (j > 0) {
prefixSum[i][j] += prefixSum[i][j - 1];
prefixSum[i][j] %= MOD;
}
}
}

// Calculate prefix sum for columns
for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
prefixSum[i][j] += prefixSum[i - 1][j];
prefixSum[i][j] %= MOD;
}
}

int[] result = new int[q];
for (int i = 0; i < q; i++) {
int top = B[i] - 1;
int left = C[i] - 1;
int bottom = D[i] - 1;
int right = E[i] - 1;

int sum = prefixSum[bottom][right];
if (top > 0) {
sum -= prefixSum[top - 1][right];
sum += MOD;
sum %= MOD;
}
if (left > 0) {
sum -= prefixSum[bottom][left - 1];
sum += MOD;
sum %= MOD;
}
if (top > 0 && left > 0) {
sum += prefixSum[top - 1][left - 1];
sum %= MOD;
}

result[i] = sum;
}

return result;
}
}``````
Python
``````MOD = 10**9 + 7

def solve(A, B, C, D, E):
n = len(A)
m = len(A[0])
q = len(B)

prefixSum = [[0 for _ in range(m)] for _ in range(n)]

# Calculate prefix sum for rows
for i in range(n):
for j in range(m):
prefixSum[i][j] = A[i][j]
if j > 0:
prefixSum[i][j] += prefixSum[i][j - 1]
prefixSum[i][j] %= MOD

# Calculate prefix sum for columns
for j in range(m):
for i in range(1, n):
prefixSum[i][j] += prefixSum[i - 1][j]
prefixSum[i][j] %= MOD

result = []
for i in range(q):
top = B[i] - 1
left = C[i] - 1
bottom = D[i] - 1
right = E[i] - 1

sum = prefixSum[bottom][right]
if top > 0:
sum -= prefixSum[top - 1][right]
sum += MOD
sum %= MOD
if left > 0:
sum -= prefixSum[bottom][left - 1]
sum += MOD
sum %= MOD
if top > 0 and left > 0:
sum += prefixSum[top - 1][left - 1]
sum %= MOD

result.append(sum)

return result``````
JavaScript
``````function solve(A, B, C, D, E) {
const MOD = 1000000007;
const n = A.length;
const m = A[0].length;
const q = B.length;

const prefixSum = new Array(n).fill(0).map(() => new Array(m).fill(0));

// Calculate prefix sum for rows
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
prefixSum[i][j] = A[i][j];
if (j > 0) {
prefixSum[i][j] += prefixSum[i][j - 1];
prefixSum[i][j] %= MOD;
}
}
}

// Calculate prefix sum for columns
for (let j = 0; j < m; j++) {
for (let i = 1; i < n; i++) {
prefixSum[i][j] += prefixSum[i - 1][j];
prefixSum[i][j] %= MOD;
}
}

const result = [];
for (let i = 0; i < q; i++) {
const top = B[i] - 1;
const left = C[i] - 1;
const bottom = D[i] - 1;
const right = E[i] - 1;

let sum = prefixSum[bottom][right];
if (top > 0) {
sum -= prefixSum[top - 1][right];
sum += MOD;
sum %= MOD;
}
if (left > 0) {
sum -= prefixSum[bottom][left - 1];
sum += MOD;
sum %= MOD;
}
if (top > 0 && left > 0) {
sum += prefixSum[top - 1][left - 1];
sum %= MOD;
}

result.push(sum);
}

return result;
}``````