前缀和相关：区域和检索 - 数组不可变、二维区域和检索 - 矩阵不可变...

给定一数组A。

前缀和：新建一数组B，数组中每一项B[i]保存A中[0…i]的和；

后缀和：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的和；

前缀积：新建一数组B，数组中每一项B[i]保存A中[0…i]的积；

后缀积：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的积；

一、区域和检索 - 数组不可变

class NumArray:
    def __init__(self, nums: List[int]):
        self.sums, pre = [0], 0
        for v in nums:
            self.sums.append(v + pre)
            pre = self.sums[-1]

    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j + 1] - self.sums[i]

二、二维区域和检索 - 矩阵不可变

核心思想：

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.sum_matrix = [[0]*(len(matrix[i])+1) for i in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                self.sum_matrix[i][j + 1] = self.sum_matrix[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sums = 0
        for i in range(row1, row2 + 1):
            sums += self.sum_matrix[i][col2 + 1] - self.sum_matrix[i][col1]
        return sums