一、一维数组度前缀和--固定数组查询区间和
1.1 定义
对于给定一个数组arr（下标从0开始），它的前缀和S[i] 表示从arr[0]到arr[i]元素总和。
1.2 构造前缀和
S[i] = S[i-1] + arr[i-1]
1.3 应用-求某个区间的和
计算区间[i, j]的元素和 => arr[i] + arr[i+1] + arr[i+2] + …… + arr[j] = s[j] - S[i-1] （i > 0) 当i== 0 时 [0, j] 元素和等于s[j]
1.4模板题
1.4.1前缀和构造 1480. 一维数组的动态和 - 力扣（LeetCode）
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
# 原地修改
for i in range(1, len(nums)):
nums[i] = nums[i-1] + nums[i]
return nums
1.4.2求区间和303. 区域和检索 - 数组不可变 - 力扣（LeetCode）
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
for i in range(1, len(nums)):
self.nums[i] = self.nums[i-1] + nums[i]
def sumRange(self, left: int, right: int) -> int:
if left == 0:
return self.nums[right]
else:
return self.nums[right] - self.nums[left-1]
二、二维度数组前缀和-固定矩阵查询子矩阵元素和
2.1 定义
定义一个矩阵matrix 使得 \(sum_i,_j\) = \(\sum_1^i\)\(\sum_1^j\)matrix[i][j]
\(sum_i,_j\) 表示已matrix[i][j] 为做右下角，matrix[1][1] 为左上角顶点围起来的矩阵元素的和
2.2 构造二维矩阵前缀和
计算公式
\[sum_i,_j = sum_{i-1},_j + sum_i,_{j-1} - sum_{i-1},_{j-1} + matrix[i][j] \]2.3 求子矩阵的区域元素和 以(\(x_1\), \(y_1\)) 为左上角 下标以(\(x_2\), \(y_2\)) 为右下角下标的区域元素和 res(x1 >= 1, y1>=1)
\[res = sum_{x2},_{y2} - sum_{x1-1},_{y2} - sum_{x2},_{y1-1} + sum_{x1-1},_{y1-1} \]2.4 模板题
2.4.1 304. 二维区域和检索 - 矩阵不可变
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.m = len(matrix) + 1
self.n = len(matrix[0]) + 1
self.sum = [[0 for i in range(self.n)] for i in range(self.m)]
for i in range(1, self.m):
for j in range(1, self.n):
# 注意matrix数组下标是从0开始, self.sum[i][j] 对应的数组右下角下标为(i-1, j-1)
self.sum[i][j] = self.sum[i-1][j] + self.sum[i][j-1] - self.sum[i-1][j-1] + matrix[i-1][j-1]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.sum[row2+1][col2+1] - self.sum[row2+1][col1] - self.sum[row1][col2+1] + self.sum[row1][col1]
三、一维差分数组
3.1 定义
对于给定一维数组arr[n], 差分数组diff[i] = arr[i] - arr[i-1] (i>1)
3.2 构造差分数组
\[diff[0] = arr[0] \]\[diff[i] = arr[i] - arr[i-1](i>0) \]3.3 应用-频繁对某个区间的元素全部增加（减少）一个值
3.3.1对于在数组[l, r]区间上所有元素都加上val，只需要在差分数组上俩端点加(减）val即可
\[diff[l] += val \]\[diff[r+1] -= val \]3.3.2 如何求得在[l, r]区间加上val后 指定arr[i] (l <= i <= r)的值，根据差分数组定义，diff[i] = arr[i] - arr[i-1] 逆运算求和即可
\[arr[i] = \sum_{j=0}^idiff[j] \]3.4 一维差分题目 1109. 航班预订统计
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
# 一开始没有预定的座位, 因此差分数组diff 为[0] * n
diff = [0] * n
# 数组从1开始, 下标处理要减少1
for first, last, incr in bookings:
diff[first-1] += incr
if last < n:
diff[last] -= incr
# 原地进行累加 arr[i] = (diff[0] + ... + diff[i-1]) + diff[i] = arr[i-1] + diff[i]
for i in range(1,n):
diff[i] += diff[i-1]
return diff
四、二维差分数组
4.1 定义 一个二维数组arr[m][n]
\[diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1](i > 1, j > 1) \]4.2以左上角下标为（x1, y1), 右下角下标（x2, y2) 区域增加（减少）一个值val
\[diff[x1][y1] += val \]\[diff[x2+1][y1] -= val \]\[diff[x1][y2+1] -= val \]\[diff[x2+1][y2+1] += val \]4.3 求区域累加后结果数组
arr[i][j] 即求差分数组diff的前缀和sum[i][j] = \(\sum_1^i\sum_1^jdiff[i][j]\)
\[arr[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + diff[i][j] \]4.4 二维差分题目 2536. 子矩阵元素加 1
class Solution:
def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
diff = [[0] * (n+2) for i in range(n+2)]
for x1, y1, x2, y2 in queries:
diff[x1+1][y1+1] += 1
diff[x2+2][y1+1] -= 1
diff[x1+1][y2+2] -= 1
diff[x2+2][y2+2] += 1
# 原地求前缀和
for i in range(1, n+1):
for j in range(1, n+1):
diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j]
diff = diff[1:-1]
for i, row in enumerate(diff):
diff[i] = row[1:-1]
return diff
```