Problem Description

The Range Sum Query 2D - Immutable problem asks you to efficiently calculate the sum of elements inside a submatrix of a given 2D matrix.
You are given a 2D matrix called matrix of size m x n. You need to implement a class NumMatrix with the following methods:

• NumMatrix(matrix): Constructor that initializes the object with the integer matrix matrix.
• sumRegion(row1, col1, row2, col2): Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2), inclusive.

• You will be given multiple sumRegion queries.
• All indices are valid.
• Matrix is immutable after initialization.

Thought Process

At first glance, you might think to simply sum up all the elements inside the given region for each sumRegion query. This brute-force approach would work, but it would be slow for large matrices and many queries.
Since the matrix is immutable (never changes after being constructed), we can precompute some helpful information to speed up our queries. The key is to avoid recalculating the sum for overlapping regions on each query.
The main idea is to use prefix sums (also known as cumulative sums) to preprocess the matrix. This allows us to answer sum queries in constant time after an initial setup.

Solution Approach

We use a 2D prefix sum (also called an integral image or summed-area table) to preprocess the matrix:

1. Build a prefix sum matrix:
   • Create a new matrix prefix of size (m+1) x (n+1).
   • For each cell (i, j) in the original matrix, set prefix[i+1][j+1] to be the sum of all elements above and to the left, including (i, j).
   • The formula is:
     prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
2. Answering a sum query:
   • To get the sum of elements in the rectangle from (row1, col1) to (row2, col2), use:
     sum = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
   • This formula uses inclusion-exclusion to subtract the extra areas and add back the overlap.
3. Why does this work?
   • The prefix sum matrix allows us to compute any submatrix sum in constant time, since each query only needs four lookups and three arithmetic operations.

Example Walkthrough

Suppose we have the following matrix:
matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ]

Let's process a query: sumRegion(2, 1, 4, 3)

• The region covers rows 2 to 4 and columns 1 to 3.
• The elements are:
  • Row 2: 2, 0, 1
  • Row 3: 1, 0, 1
  • Row 4: 0, 3, 0
• Sum: 2+0+1 + 1+0+1 + 0+3+0 = 8

• We look up prefix[5][4] (sum of everything up to row 4, col 3)
• Subtract prefix[2][4] (above region)
• Subtract prefix[5][1] (left of region)
• Add back prefix[2][1] (overlap)
• This gives us the sum in constant time!

Time and Space Complexity

• Brute-force approach:
  • Each sumRegion query: O(R*C), where R and C are the number of rows and columns in the region.
  • For many queries, this is slow.
• Optimized (Prefix Sum) approach:
  • Preprocessing: O(m*n) time and space to build the prefix sum matrix.
  • Each sumRegion query: O(1) time (just four lookups and a few additions/subtractions).
  • Space: O(m*n) for the prefix sum matrix.

Summary

The key to efficiently solving the Range Sum Query 2D - Immutable problem is recognizing that the matrix does not change, so we can preprocess cumulative sums. By building a 2D prefix sum matrix, we turn each region sum query from a potentially slow operation into a lightning-fast constant time calculation. This approach is elegant, efficient, and leverages the power of precomputation for immutable data.

Code Implementation

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            self.prefix = []
            return
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                self.prefix[i+1][j+1] = (
                    matrix[i][j]
                    + self.prefix[i][j+1]
                    + self.prefix[i+1][j]
                    - self.prefix[i][j]
                )

    def sumRegion(self, row1, col1, row2, col2):
        return (
            self.prefix[row2+1][col2+1]
            - self.prefix[row1][col2+1]
            - self.prefix[row2+1][col1]
            + self.prefix[row1][col1]
        )
      

class NumMatrix {
public:
    vector<vector<int>> prefix;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = m ? matrix[0].size() : 0;
        prefix = vector<vector<int>>(m+1, vector<int>(n+1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                prefix[i+1][j+1] = matrix[i][j]
                    + prefix[i][j+1]
                    + prefix[i+1][j]
                    - prefix[i][j];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2+1][col2+1]
             - prefix[row1][col2+1]
             - prefix[row2+1][col1]
             + prefix[row1][col1];
    }
};
      

class NumMatrix {
    private int[][] prefix;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = m == 0 ? 0 : matrix[0].length;
        prefix = new int[m+1][n+1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                prefix[i+1][j+1] = matrix[i][j]
                    + prefix[i][j+1]
                    + prefix[i+1][j]
                    - prefix[i][j];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2+1][col2+1]
             - prefix[row1][col2+1]
             - prefix[row2+1][col1]
             + prefix[row1][col1];
    }
}
      

var NumMatrix = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        this.prefix = [];
        return;
    }
    let m = matrix.length, n = matrix[0].length;
    this.prefix = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            this.prefix[i+1][j+1] = matrix[i][j]
                + this.prefix[i][j+1]
                + this.prefix[i+1][j]
                - this.prefix[i][j];
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.prefix[row2+1][col2+1]
         - this.prefix[row1][col2+1]
         - this.prefix[row2+1][col1]
         + this.prefix[row1][col1];
};