# Range Sum Query 2D - Immutable
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/range-sum-query-2d-immutable)
Canonical: https://scaleengineer.com/dsa/problems/range-sum-query-2d-immutable
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Nvidia](https://scaleengineer.com/companies/nvidia), [Snowflake](https://scaleengineer.com/companies/snowflake), [Lyft](https://scaleengineer.com/companies/lyft), [Upstart](https://scaleengineer.com/companies/upstart), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition)
---
## Problem
Given a 2D matrix `matrix`, handle multiple queries of the following type:

* Calculate the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

Implement the `NumMatrix` class:

* `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
* `int sumRegion(int row1, int col1, int row2, int 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)`.

You must design an algorithm where `sumRegion` works on `O(1)` time complexity.

**Example 1:**

![](https://assets.glich.co/dsa/range-sum-query-2d-immutable/image0.jpg) 

**Input**
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
**Output**
[null, 8, 11, 12]

**Explanation**
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 200`
* `-104 <= matrix[i][j] <= 104`
* `0 <= row1 <= row2 < m`
* `0 <= col1 <= col2 < n`
* At most `104` calls will be made to `sumRegion`.

# Approaches
## Brute Force - Direct Calculation
The most straightforward approach is to calculate the sum for each query by iterating through all elements in the specified rectangle. For each `sumRegion` call, we traverse the matrix from `(row1, col1)` to `(row2, col2)` and accumulate the sum.
**Time:** O(1) for constructor, O(m*n) for sumRegion in worst case where m and n are the dimensions of the query rectangle · **Space:** O(1) additional space (only storing reference to original matrix)
**Pros:** Simple and straightforward implementation; No additional space required beyond storing the original matrix; Easy to understand and debug
**Cons:** Does not meet the O(1) requirement for sumRegion; Inefficient for multiple queries as it recalculates the same sums; Performance degrades significantly with larger query rectangles
### Explanation
This approach directly calculates the sum for each query without any preprocessing. When `sumRegion(row1, col1, row2, col2)` is called, we iterate through all rows from `row1` to `row2` and all columns from `col1` to `col2`, adding each element to our running sum.

```java
class NumMatrix {
    private int[][] matrix;
    
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                sum += matrix[i][j];
            }
        }
        return sum;
    }
}
```

This approach is simple to implement and understand, but it doesn't meet the O(1) requirement for `sumRegion` operations.
### Algorithm
1. Store the original matrix in the constructor
2. For each `sumRegion` query:
   - Initialize sum to 0
   - Iterate through rows from row1 to row2
   - For each row, iterate through columns from col1 to col2
   - Add each element to the sum
   - Return the accumulated sum

## Row-wise Prefix Sum
This approach preprocesses each row to store cumulative sums, allowing us to calculate the sum of any row segment in O(1) time. For each query, we sum up the contributions from each row in the specified range.
**Time:** O(m*n) for constructor, O(m) for sumRegion where m is the number of rows in the query · **Space:** O(m*n) for storing the prefix sum array
**Pros:** Better than brute force for wide rectangles; Each row sum calculation is O(1); Relatively simple to implement and understand
**Cons:** Still doesn't achieve O(1) for sumRegion; Uses additional space proportional to the matrix size; Performance depends on the height of the query rectangle
### Explanation
We precompute prefix sums for each row during initialization. For each row, we store cumulative sums from the beginning of the row to each column. When answering a query, we iterate through each row in the range and use the precomputed prefix sums to get the sum of the column range in O(1) time per row.

```java
class NumMatrix {
    private int[][] prefixSum;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        
        int m = matrix.length;
        int n = matrix[0].length;
        prefixSum = new int[m][n + 1]; // Extra column for easier calculation
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += prefixSum[i][col2 + 1] - prefixSum[i][col1];
        }
        return sum;
    }
}
```

This approach reduces the time complexity of sumRegion compared to brute force, but still doesn't achieve O(1) as required.
### Algorithm
1. During initialization:
   - Create a 2D prefix sum array with an extra column
   - For each row, compute cumulative sums from left to right
2. For each `sumRegion` query:
   - Initialize sum to 0
   - For each row from row1 to row2:
     - Add the difference between prefix sums at col2+1 and col1
   - Return the accumulated sum

## 2D Prefix Sum (Optimal)
This approach uses 2D prefix sums to precompute the sum of all rectangles from (0,0) to any point (i,j). Using the inclusion-exclusion principle, we can calculate any rectangle sum in O(1) time by combining four prefix sum values.
**Time:** O(m*n) for constructor, O(1) for sumRegion · **Space:** O(m*n) for storing the 2D prefix sum array
**Pros:** Achieves O(1) time complexity for sumRegion as required; Efficient for multiple queries; Mathematically elegant solution using inclusion-exclusion principle
**Cons:** Requires additional space proportional to matrix size; More complex to implement correctly (easy to make off-by-one errors); Preprocessing time is proportional to matrix size
### Explanation
We create a 2D prefix sum array where `prefixSum[i][j]` represents the sum of all elements in the rectangle from `(0,0)` to `(i-1,j-1)`. To calculate the sum of a rectangle from `(row1,col1)` to `(row2,col2)`, we use the inclusion-exclusion principle:

`sum = prefixSum[row2+1][col2+1] - prefixSum[row1][col2+1] - prefixSum[row2+1][col1] + prefixSum[row1][col1]`

```java
class NumMatrix {
    private int[][] prefixSum;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        
        int m = matrix.length;
        int n = matrix[0].length;
        prefixSum = new int[m + 1][n + 1]; // Extra row and column for easier calculation
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + 
                                 prefixSum[i][j-1] - prefixSum[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - 
               prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }
}
```

This approach achieves the required O(1) time complexity for sumRegion operations by leveraging the mathematical property that any rectangle sum can be computed using four corner values from the prefix sum array.
### Algorithm
1. During initialization:
   - Create a 2D prefix sum array with extra row and column (filled with zeros)
   - For each cell (i,j), compute prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
2. For each `sumRegion` query:
   - Apply inclusion-exclusion principle using four corner values from prefix sum array
   - Return the result in O(1) time

# Solutions
### Java

```java
class NumMatrix { private int [][] s ; public NumMatrix ( int [][] matrix ) { int m = matrix . length , n = matrix [ 0 ]. length ; s = new int [ m + 1 ][ n + 1 ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] + s [ i ][ j + 1 ] - s [ i ][ j ] + matrix [ i ][ j ]; } } } public int sumRegion ( int row1 , int col1 , int row2 , int col2 ) { return s [ row2 + 1 ][ col2 + 1 ] - s [ row2 + 1 ][ col1 ] - s [ row1 ][ col2 + 1 ] + s [ row1 ][ col1 ]; } } /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj = new NumMatrix(matrix); * int param_1 = obj.sumRegion(row1,col1,row2,col2); */
```

### JavaScript

```javascript
/** * @param {number[][]} matrix */ var NumMatrix = function ( matrix ) { const m = matrix . length ; const n = matrix [ 0 ]. length ; this . s = new Array ( m + 1 ). fill ( 0 ). map (() => new Array ( n + 1 ). fill ( 0 )); for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { this . s [ i + 1 ][ j + 1 ] = this . s [ i + 1 ][ j ] + this . s [ i ][ j + 1 ] - this . s [ i ][ j ] + matrix [ i ][ j ]; } } }; /** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2 * @return {number} */ NumMatrix . prototype . sumRegion = function ( row1 , col1 , row2 , col2 ) { return ( this . s [ row2 + 1 ][ col2 + 1 ] - this . s [ row2 + 1 ][ col1 ] - this . s [ row1 ][ col2 + 1 ] + this . s [ row1 ][ col1 ] ); }; /** * Your NumMatrix object will be instantiated and called as such: * var obj = new NumMatrix(matrix) * var param_1 = obj.sumRegion(row1,col1,row2,col2) */
```

### CPP

```cpp
class NumMatrix { public: vector < vector < int >> s ; NumMatrix ( vector < vector < int >>& matrix ) { int m = matrix . size (), n = matrix [ 0 ]. size (); s . resize ( m + 1 , vector < int > ( n + 1 )); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] + s [ i ][ j + 1 ] - s [ i ][ j ] + matrix [ i ][ j ]; } } } int sumRegion ( int row1 , int col1 , int row2 , int col2 ) { return s [ row2 + 1 ][ col2 + 1 ] - s [ row2 + 1 ][ col1 ] - s [ row1 ][ col2 + 1 ] + s [ row1 ][ col1 ]; } }; /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */
```

### Python

```python
''' >>> a = [ [1,2,3], [4,5,6] ] >>> b = a.copy() >>> b [[1, 2, 3], [4, 5, 6]] ''' class NumMatrix : def __init__ ( self , matrix : List [ List [ int ]]): m , n = len ( matrix ), len ( matrix [ 0 ]) self . s = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for i , row in enumerate ( matrix ): for j , v in enumerate ( row ): self . s [ i + 1 ][ j + 1 ] = ( self . s [ i ][ j + 1 ] + self . s [ i + 1 ][ j ] - self . s [ i ][ j ] + v ) def sumRegion ( self , row1 : int , col1 : int , row2 : int , col2 : int ) -> int : return ( self . s [ row2 + 1 ][ col2 + 1 ] - self . s [ row2 + 1 ][ col1 ] - self . s [ row1 ][ col2 + 1 ] + self . s [ row1 ][ col1 ] ) # Your NumMatrix object will be instantiated and called as such: # obj = NumMatrix(matrix) # param_1 = obj.sumRegion(row1,col1,row2,col2) ############ class NumMatrix ( object ): def __init__ ( self , matrix ): """ initialize your data structure here. :type matrix: List[List[int]] """ self . dp = [[ 0 ] * len ( matrix [ 0 ]) for i in range ( 0 , len ( matrix ))] for i in range ( 0 , len ( matrix )): for j in range ( 0 , len ( matrix [ 0 ])): if i == 0 : self . dp [ 0 ][ j ] = self . dp [ 0 ][ j - 1 ] + matrix [ i ][ j ] elif j == 0 : self . dp [ i ][ 0 ] = self . dp [ i - 1 ][ 0 ] + matrix [ i ][ j ] else : self . dp [ i ][ j ] = self . dp [ i - 1 ][ j ] + self . dp [ i ][ j - 1 ] - self . dp [ i - 1 ][ j - 1 ] + matrix [ i ][ j ] def sumRegion ( self , row1 , col1 , row2 , col2 ): """ sum of elements matrix[(row1,col1)..(row2,col2)], inclusive. :type row1: int :type col1: int :type row2: int :type col2: int :rtype: int """ dp = self . dp diagSum = dp [ row1 - 1 ][ col1 - 1 ] totalSum = dp [ row2 ][ col2 ] leftSum = dp [ row2 ][ col1 - 1 ] upSum = dp [ row1 - 1 ][ col2 ] if row1 == 0 : upSum = 0 diagSum = 0 if col1 == 0 : leftSum = 0 diagSum = 0 return totalSum - leftSum - upSum + diagSum
```