一维前缀和

 S[i] = a[1] + a[2] + ... a[i]
 a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

 S[i, j] = 第i行j列格子左上部分所有元素的和
 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
 S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分

 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
 S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

[https://leetcode-cn.com/problems/stamping-the-grid/](力扣 69 双周赛第 4 题)

class Solution {
public:
    vector<vector<int>> built(vector<vector<int> >& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> sum(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                sum[i + 1][j + 1] = grid[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
            }
        }
        return sum;
    }
    int query(vector<vector<int>>& sum, int x1, int y1, int x2, int y2) {
        return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    }
    bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
        auto sum = built(grid);
        int n = grid.size(), m = grid[0].size();
        vector<vector<int> > paint(n, vector<int>(m));

        for (int i = 0; i + h <= n; ++ i) {
            for (int j = 0; j + w <= m; ++ j) {
                if (grid[i][j] == 0 && query(sum, i + 1, j + 1, i + h, j + w) == 0) 
                    paint[i][j] = 1;
            }
        }
        auto psum = built(paint);
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (grid[i][j] == 0 && query(psum, max(1, i - h + 2), max(1, j - w + 2), i + 1, j + 1) == 0) 
                    return false;
            }
        }
        return true;

    }
};