Problem Statement

Given an n×m integer matrix and q queries, each query specifies the coordinates of the top-left and bottom-right corners of a submatrix. For each query, compute the sum of all elements within the specified submatrix.

Solution Approach

The problem can be efficiently solved using 2D prefix sums. By precomputing the cumulative sum matrix, each query can be answered in constant time O(1).

The prefix sum array S is constructed such that S[i][j] represents the sum of all elements in the rectangle from (1,1) to (i,j). The sum of any submatrix with corners at (x1,y1) and (x2,y2) can then be computed using the inclusion-exclusion principle:

Submatrix Sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

Implementation Examples

C++ Solution

#include <iostream>
using namespace std;

const int MAX_SIZE = 1010;
int prefixSum[MAX_SIZE][MAX_SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int rows, cols, queries;
    cin >> rows >> cols >> queries;
    
    // Build prefix sum matrix
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            int value;
            cin >> value;
            prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] 
                            - prefixSum[i-1][j-1] + value;
        }
    }
    
    // Process queries
    for (int i = 0; i < queries; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int result = prefixSum[x2][y2] - prefixSum[x1-1][y2] 
                   - prefixSum[x2][y1-1] + prefixSum[x1-1][y1-1];
        cout << result << "\n";
    }
    
    return 0;
}

Go Solution

package main

import (
    "fmt"
)

func main() {
    var rows, cols, queries int
    fmt.Scan(&rows, &cols, &queries)
    
    // Initialize prefix sum matrix
    prefixMatrix := make([][]int, rows+1)
    for i := range prefixMatrix {
        prefixMatrix[i] = make([]int, cols+1)
    }
    
    // Build prefix sums
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            var val int
            fmt.Scan(&val)
            prefixMatrix[i][j] = prefixMatrix[i-1][j] + prefixMatrix[i][j-1] 
                               - prefixMatrix[i-1][j-1] + val
        }
    }
    
    // Handle queries
    for i := 0; i < queries; i++ {
        var x1, y1, x2, y2 int
        fmt.Scan(&x1, &y1, &x2, &y2)
        sum := prefixMatrix[x2][y2] - prefixMatrix[x1-1][y2] 
             - prefixMatrix[x2][y1-1] + prefixMatrix[x1-1][y1-1]
        fmt.Println(sum)
    }
}

Input/Output Example

Sample Input:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

Sample Output:

17
27
21

Constraints

• Matrix dimensions: 1 ≤ rows, cols ≤ 1000
• Number of queries: 1 ≤ queries ≤ 200000
• Coordinate bounds: 1 ≤ x1 ≤ x2 ≤ rows, 1 ≤ y1 ≤ y2 ≤ cols
• Element values: -1000 ≤ matrix[i][j] ≤ 1000