前缀和+差分数组

一、一维数组度前缀和--固定数组查询区间和

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 构造二维矩阵前缀和

计算公式

2.3 求子矩阵的区域元素和 以(\(x_1\), \(y_1\)) 为左上角 下标以(\(x_2\), \(y_2\)) 为右下角下标的区域元素和 res(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 构造差分数组

3.3 应用-频繁对某个区间的元素全部增加（减少）一个值

3.3.1对于在数组[l, r]区间上所有元素都加上val，只需要在差分数组上俩端点加(减）val即可

3.3.2 如何求得在[l, r]区间加上val后 指定arr[i] (l <= i <= r)的值，根据差分数组定义，diff[i] = arr[i] - arr[i-1] 逆运算求和即可

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]

4.2以左上角下标为（x1, y1), 右下角下标（x2, y2) 区域增加（减少）一个值val

4.3 求区域累加后结果数组

arr[i][j] 即求差分数组diff的前缀和sum[i][j] = \(\sum_1^i\sum_1^jdiff[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
	```

本栏目推荐文章
• 类模板实现简单的数组
• 数组内存图
• 数组
• 前缀集合相等
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• linux ubantu新建用户su后不显示用户名、路径等前缀问题解决方案
• 吴师兄学算法day06 双指针 80. 合并两个有序数组
• C# 方法中的参数数组
• 吴师兄学算法day06 双指针 26. 删除有序数组中的重复项
• 打印稀疏数组

前缀 数组前缀 数组php元素 偏序 前缀 数组codeforces 前缀 数组 问题560 前缀 数组leetcode两个 前缀 数组 算法 技巧 前缀 数组labuladong技巧 前缀 数组leetcode 523 前缀 数组 算法 前缀 数组 前缀