前缀和 & 差分

一维差分

不支持边修边查，核心思想是最后统一修改。

需要注意，对$L-R$段处理时，最右端消除影响的纪录应该在差分数组的R+1位置进行记录，同时要注意处理$R$为最后位置时可能出现的越界情况。

例题

实现代码：

点击展开代码

class Solution {
public:


    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

        vector<int> res(n,0);
        for(auto b:bookings){
            res[b[0]-1]+=b[2];       //因为给定数据范围是1-n，但数组只开了n，下标范围是0-（n-1），所以这里索引要-1
            if(b[1]==n)continue;     //为了防止越界，如果右端是最后一个点直接跳过，因为不再需要处理了
            else res[b[1]]-=b[2];
        }

        for(int i=1;i<n;i++){
           res[i]=res[i]+res[i-1]; 
        }

        return res;
    }
};

等差数列一维差分

已知数组arr，对其进行$k$次操作，每次操作选取左右两个端点，给定一个相同长度的等差数列[s,e,d]表示数列首尾和公差，一一对应加在选取的区间上，求多次操作后的结果。

本质上是两次一维差分，和一维差分相同，不支持边查边改；在每次操作的预处理中和一维差分有所区别，执行以下四步：

arr[l]+=s
arr[l+1]+=d-s
arr[r+1]-=d+e
arr[r+2]+=e

二维前缀和

二维前缀和的题目通常为给定一个矩阵matrix，求其中某个矩形区域的和。

思路为预处理时每个节点记录以[0,0]为左上角、该节点为右下角的矩阵的总和；对于每个元素[x,y]，其值为matrix[x][y]+pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]，需要额外注意边界的情况。

例题

前缀和

题目链接：304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

点击展开题目

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 1：

输入: ["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]] 输出: [null, 8, 11, 12]

解释: NumMatrix numMatrix = new NumMatrix([[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]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

实现代码

点击展开代码

class NumMatrix {
public:
    int pre[205][205];
    NumMatrix(vector<vector<int>>& matrix) {
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                int sum=matrix[i][j];
                if(i!=0)sum+=pre[i-1][j];
                if(j!=0)sum+=pre[i][j-1];
                if(i!=0 && j!=0)sum-=pre[i-1][j-1];
                pre[i][j]=sum;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int res=pre[row2][col2];
        if(row1>0)res-=pre[row1-1][col2];
        if(col1>0)res-=pre[row2][col1-1];
        if(row1>0&&col1>0)res+=pre[row1-1][col1-1];
        return res;
    }
};

矩形检查

二维差分

在遇到二维矩阵+区域覆盖时考虑二维差分，总体思路是对数据进行预处理后进行二维前缀和，得到的就是每个元素的变化值。

给定矩阵$matrix$，进行$k$次操作，每次操作对以$[lx,ly]$和 $[rx,ry]$分别为左上顶点和右下顶点的矩形区域中的每个值加$v$，则进行以下预处理：

pre[lx][ly]+=v
pre[lx][ry+1]-=v
pre[rx+1][ly]-=v
pre[rx+1][ry+1]+=v

例题

题目链接：2132. 用邮票贴满网格图 - 力扣（LeetCode）

点击展开题目

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。

给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：

覆盖所有空格子。
不覆盖任何 被占据 的格子。
我们可以放入任意数目的邮票。
邮票可以相互有重叠部分。
邮票不允许旋转。
邮票必须完全在矩阵内。

如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
输出：false 
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 105
1 <= m * n <= 2 * 105
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 105

实现代码

点击展开代码

class Solution {
public:
    //二维差分+前缀和，前缀和预处理，遍历每个空节点，根据前缀和判断能否贴，能贴就进差分数组
    //处理差分数组，遍历原数组，如果两个值全为0，则返回false

    int n,m;

    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        n=grid.size();
        m=grid[0].size();

        vector<vector<int>> pre(n,vector<int>(m,0));
        vector<vector<int>> diff(n,vector<int>(m,0));

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                pre[i][j]=grid[i][j];
                if(i>0)pre[i][j]+=pre[i-1][j];
                if(j>0)pre[i][j]+=pre[i][j-1];
                if(i>0&&j>0)pre[i][j]-=pre[i-1][j-1];
            }
        }

        //遍历所有为0的节点并根据前缀和检查是否能贴
        for(int i=0;i<n;i++){
                int rx=i+stampHeight-1;
                if(rx>=n)break;
            for(int j=0;j<m;j++){
                int ry=j+stampWidth-1;
                if(ry>=m)break;

                int curr=pre[rx][ry];
                if(i>0)curr-=pre[i-1][ry];
                if(j>0)curr-=pre[rx][j-1];
                if(i>0&&j>0)curr+=pre[i-1][j-1];

                //差分对比
                if(curr==0){
                    diff[i][j]+=1;
                    if(ry+1<m)diff[i][ry+1]-=1;
                    if(rx+1<n)diff[rx+1][j]-=1;
                    if(rx+1<n&&ry+1<m)diff[rx+1][ry+1]+=1;
                }
            }
        }

        //差分整理
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i>0)diff[i][j]+=diff[i-1][j];
                if(j>0)diff[i][j]+=diff[i][j-1];
                if(i>0&&j>0)diff[i][j]-=diff[i-1][j-1];
            }
        }

        //检查判断
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]!=0)continue;
                if(diff[i][j]==0)return false;
            }
        }

        return true;
    }

};