To efficiently compute the sum of elements in any submatrix of a given 2D grid, we use a two-dimensional prefix sum technique. This approach allows each query to be anwsered in constant time after an initial preprocessing step.

Core Idea

We constrcut a prefix sum matrix pref where pref[i][j] represents the sum of all elements in the rectangle from the top-left corner (0, 0) to (i-1, j-1) in the original matrix. To simplify boundary handling, we pad the prefix matrix with an extra row and column of zeros at the top and left.

The recurrence relation for building the prefix matrix is:

pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + matrix[i-1][j-1]

Querying Submatrix Sum

Given a query rectangle defined by its top-left corner (r1, c1) and bottom-right corner (r2, c2) (using 0-based indexing in the original matrix), we first adjust these coordinates to match the padded prefix matrix by incrementing each by 1.

The sum of the submatrix is then computed as:

sum = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<long long>> mat(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> mat[i][j];

    vector<vector<long long>> pref(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + mat[i][j];

    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        // Convert to 1-based indices in pref
        long long ans = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1];
        cout << ans << '\n';
    }
    return 0;
}

Java Implementation

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        long[][] pref = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                pref[i][j] = sc.nextLong();
            }
        }

        // Build prefix sum in-place
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
            }
        }

        while (q-- > 0) {
            int r1 = sc.nextInt();
            int c1 = sc.nextInt();
            int r2 = sc.nextInt();
            int c2 = sc.nextInt();
            long result = pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
            System.out.println(result);
        }
    }
}