前缀和 && 差分

差分和前缀和都是算法里边比较重要的知识点，不过学习的难度并不高，这篇文章会讲解相关的内容。

1. 前缀和怎么玩

1）一维前缀和

在该数之前，包括该数的所有数之和，有点类似高中学的数列的前n项和Sn。

2）二维前缀和

根据原数组生成sum数组，sum[i][j]表示从(0, 0)到(i, j)这个范围内的累加和

求法：依次求 左 + 上 - 左上 + 自己，再从左到右，从上到下生成

*往往补第0行、第0列来减少条件判断

【图解】

Q：如果要求某个范围内的累加和怎么办？

设求(a, b)到(c, d)的累加和，则累加和就是

sum[c][d] - sum[a-1][d] - sum[c][b-1] + sum[a-1][b-1]

根据sum数组的定义和下面的图解就非常清晰了

图解如下：

【练习】

有一道模版题，大家可以试着做做：链接

核心的思路就是二维前缀和，我的代码如下： 

class NumMatrix {
public:
    vector<vector<int>> sum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        sum.resize(m + 1, vector<int>(n + 1));
        
        // 第0行、第0列空出来，减少判断
        for (int a = 0, b = 1; a < m; a++, b++)
            for (int c = 0, d = 1; c < n; c++, d++)
                sum[b][d] = matrix[a][c];
        
        // 求前缀和
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                sum[i][j] += sum[i - 1][j] +
                sum[i][j - 1] - sum[i - 1][j - 1];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        row2++;
        col2++;
        return sum[row2][col2] - sum[row2][col1]
            - sum[row1][col2] + sum[row1][col1];
    }
};

2. 差分怎么玩

前缀和是为了下面学习差分做铺垫的，那么差分是什么玩意呢？

一般来说，差分分为3种类型，分别是一维差分、二维差分、等差差分

1）一维差分

首先，来看一个例子：

给定一个开始全为0的数组(设大小为8)，在指定下标范围进行加减操作，求多次操作后的数组

分别对2～5下标对应的数进行加3，1～3下标加2，4～6下标减2

当然，你也可以每个动作都循环一次，但是那样代码写得有点挫，而差分就是解决这样一类的问题的好方法。

【使用方式】

在每个动作的左位置下标做对应的操作，在右位置的下一个数进行逆操作，所有操作一遍后，用前缀和加工。

这是什么意思，说的是人话吗？🤔

比如，对2～5下标对应的数进行加3，那么就在2位置加3，在6位置减3；(此为一次操作)

对1～3位置加2，就对应着1位置加2，4位置减2；(第二次操作)

对4～6位置减2，对应4位置减2，7位置加2。(第三次操作)

最后进行前缀和加工(此步骤可以在多次操作后进行)

【图解】

【原理】

操作方式就是如上，原理也很简单，因为一开始全是0，那么在进行前缀和操作时就不会受到初始值的影响，只会由我们自己的操作控制。

而在第一个位置加了3，那么经过前缀和的操作就会让该位置及其后的位置都加了3，而因为在最右的位置在往后就不用操作了，那么就需要它的逆操作来抵消了。

【练习】

leetcode_1109航班预订

核心思路就是一维差分 + 前缀和加工，其实就相当于模版题了

参考代码：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> sum(n + 2, 0);
        for(int i = 0; i < bookings.size(); i++)
        {
            sum[bookings[i][0]] += bookings[i][2];
            sum[bookings[i][1] + 1] -= bookings[i][2];
        }

        vector<int> ans;
        for(int i = 1; i <= n; i++)
        {
            sum[i] += sum[i - 1];
            ans.push_back(sum[i]);
        }
        
        return ans;
    }
};

2）二维差分

跟一维差分类似，也是在初始全为0的条件下，然后在给定两个坐标区间，进行加减操作，多次操作后，求变化后的数组

【使用方式】

设 (a, b) 到 (c, d) 的范围 + v

一次操作：  (a, b) + v 

(a, d+1) - v

(c+1, b) - v

(c+1, d+1) + v

···（多次操作）

最后要加工前缀和

其实原理跟一维差分是类似的，也是因为在前缀和的加工后，对于某个点的变化就成了一片区域的变化，而对于重叠的变化(减了2次)需要再处理

【图解】

【练习】

leetcode_2132贴邮票

核心：二维前缀和与二维差分的结合

思考逻辑：先不考虑邮票的重叠，直接把能贴的位置都贴上，其中判断能不能贴是根据区域前缀和是否为0，贴邮票是二维差分的过程(对应四角处理)，最后再前缀和加工

注意：此题要非常注意数组的范围，不然会越界

参考代码：链接（内含注释）

3）等差差分

这类问题相当考的较少，可以考虑先跳过

一般的问题描述是，一开始数组全为0，接下来有若干次(已知)操作，每次操作分别是在 l～r 范围上依次加上首项为s，末项为e，公差为d的等差数列，求多次操作后的数组

【使用方式】

arr[l] += s

arr[l + 1] += d - s

arr[r + 1] -= d + e

arr[r + 2] += e

多次操作后，再加工两次前缀和

【图解】

【练习】

luogu_P4231三步必杀

其实就是模板题，思路不难

注意数据量比较大，要用 long long

参考代码：链接

如果有问题可以在评论区一起讨论，对你有帮助的话不妨点个赞👍