​LeetCode刷题实战304：二维区域和检索 - 矩阵不可变

给定 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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

class NumMatrix:


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


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

class NumMatrix:


def __init__(self, matrix: List[List[int]]):
self._matrix = matrix




def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
result = 0
"""
        for row in self._matrix[row1:row2+1]:
            for col in row[col1:col2+1]:
                result += col
        """
for i in range(row1, row2+1):
for j in range(col1, col2+1):
result += self._matrix[i][j]
return result