**Solution**

**Range Sum Query 2D - Immutable** https://leetcode.com/problems/range-sum-query-2d-immutable/

**Refer Editorial to for solutions: All worth it**

- Naive - compute at run time
- Pre-compute every possibility = m^2 * n^2
- Build a cdf array row or column wise. Depending on this choice, the run time complexity will matter - will be either O(m) or O(n). If rows are more, choose caching row wise so that query complexity is column wise.
- Optimized caching - caching with respect to index 0,0.

Notice the DP equation to compute: Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

Notice also the code to build the matrix uses DP - dp[r + 1,c + 1] = dp[r + 1,c] + dp[r,c + 1] + matrix[r,c] - dp[r,c];

```
class NumMatrix(object):
def __init__(self, matrix):
"""
initialize your data structure here.
:type matrix: List[List[int]]
"""
M = len(matrix)
if M == 0:
return
N = len(matrix[0])
self.cdf = [[0]*N for _ in range(M)]
self.matrix = matrix
# Column wise cache
for j in range(N):
for i in range(M):
if i == 0:
self.cdf[i][j] = matrix[i][j]
else:
self.cdf[i][j] = self.cdf[i-1][j] + matrix[i][j]
return
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
"""
result = 0
for col in range(col1, col2+1):
result = result + self.cdf[row2][col]-self.cdf[row1][col]+self.matrix[row1][col]
return result
```