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;
}

Spiral Order Matrix Ii Sum of All Submatrices