二维前缀和
304. 二维区域和检索 - 矩阵不可变
二位前缀和目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是 O(1) 的操作
-
根据原始状况，生成二维前缀和数组sum，
sum[i][j]: 代表左上角 (0,0) 到右下角 (i,j) 这个范围的累加和sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]; -
查询左上角 (a,b) 到右下角 (c,d) 这个范围的累加和
sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]; -
实际过程中往往补第 0 行、第 0 列来减少很多条件判断。
#include <vector>using namespace std;class NumMatrix {
public:vector<vector<int>> sum;NumMatrix(vector<vector<int>> &matrix) {int n = matrix.size();int m = matrix[0].size();// 矩阵扩大，减少边界讨论sum.resize(n + 1, vector<int>(m + 1));// 原始矩阵拷贝到扩大后的矩阵for (int a = 1, c = 0; c < n; a++, c++)for (int b = 1, d = 0; d < m; b++, d++)sum[a][b] = matrix[c][d];// 计算二维前缀和for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - 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];}
};
1139. 最大的以 1 为边界的正方形
#include <vector>using namespace std;class Solution {
public:// 越界就返回 0int get(vector<vector<int>> &grid, int i, int j) {return (i < 0 || j < 0) ? 0 : grid[i][j];}// 把原始矩阵变成二位前缀和矩阵void build(int n, int m, vector<vector<int>> &grid) {for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)grid[i][j] += get(grid, i, j - 1) + get(grid, i - 1, j) - get(grid, i - 1, j - 1);}// 返回子矩阵的和int sum(vector<vector<int>> &grid, int a, int b, int c, int d) {return a > c ? 0 : (grid[c][d] - get(grid, c, b - 1) - get(grid, a - 1, d) + get(grid, a - 1, b - 1));}// 时间复杂度 O(n * m * min(n,m))，额外空间复杂度 O(1)int largest1BorderedSquare(vector<vector<int>> &grid) {int n = grid.size();int m = grid[0].size();build(n, m, grid);// 矩阵里面全是 0if (sum(grid, 0, 0, n - 1, m - 1) == 0) return 0;// 找到的最大合法正方形的边长int len = 1;// (a,b) 所有左上角点，(c,d) 更大边长的右下角点，k 是当前尝试的边长for (int a = 0; a < n; a++)for (int b = 0; b < m; b++)// 从 len + 1 找是为了剪枝，只需要找更长的边长for (int c = a + len, d = b + len, k = len + 1; c < n && d < m; c++, d++, k++)// 如果面积差为周长，说明有一圈 1if (sum(grid, a, b, c, d) - sum(grid, a + 1, b + 1, c - 1, d - 1) == (k - 1) << 2)len = k;return len * len;}
};
二维差分
在二维数组中，如果经历如下的过程
- 批量的做如下的操作，每个操作都有独立的 a、b、c、d、v
void add(a, b, c, d, v) : 左上角 (a,b) 到右下角 (c,d) 范围上，每个数字 +v
// 只对四个点操作
void add(int a, int b, int c, int d, int v) {diff[a][b] += v;diff[c + 1][b] -= v;diff[a][d + 1] -= v;diff[c + 1][d + 1] += v;
}
// 构建二维前缀和
void build() {for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
}
- 给矩阵加一圈 0 可以避免边界讨论
【模板】二维差分
#include <iostream>using namespace std;const int MAX_N = 1005;
const int MAX_M = 1005;// 二维差分数组
long long diff[MAX_N][MAX_M];
int n, m, q;// 二维差分，对四个点操作
void add(int a, int b, int c, int d, int k) {diff[a][b] += k;diff[c + 1][b] -= k;diff[a][d + 1] -= k;diff[c + 1][d + 1] += k;
}// 计算二维前缀和
void build() {for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
}void clear() {for (int i = 1; i <= n + 1; i++)for (int j = 1; j <= m + 1; j++)diff[i][j] = 0;
}int main() {while (cin >> n >> m >> q) {// 实际矩阵外围有一圈 0，避免边界讨论for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int value;cin >> value;add(i, j, i, j, value);}}// 二维差分for (int i = 1, a, b, c, d, k; i <= q; i++) {cin >> a >> b >> c >> d >> k;add(a, b, c, d, k);}build();// 打印结果for (int i = 1; i <= n; i++) {cout << diff[i][1];for (int j = 2; j <= m; j++)cout << " " << diff[i][j];cout << endl;}clear();}return 0;
}
P3397 地毯
#include <iostream>using namespace std;const int MAXN = 1002;
int diff[MAXN][MAXN];
int n, q;void add(int a, int b, int c, int d, int k) {diff[a][b] += k;diff[c + 1][b] -= k;diff[a][d + 1] -= k;diff[c + 1][d + 1] += k;
}void build() {for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
}void clear() {for (int i = 1; i <= n + 1; i++)for (int j = 1; j <= n + 1; j++)diff[i][j] = 0;
}int main() {while (cin >> n >> q) {for (int i = 1, a, b, c, d; i <= q; i++) {cin >> a >> b >> c >> d;add(a, b, c, d, 1);}build();for (int i = 1; i <= n; i++) {cout << diff[i][1];for (int j = 2; j <= n; j++) {cout << " " << diff[i][j];}cout << endl;}clear();}return 0;
}
2132. 用邮票贴满网格图
#include <iostream>
#include <vector>using namespace std;class Solution {
public:void add(vector<vector<int>> &diff, int a, int b, int c, int d) {diff[a][b] += 1;diff[c + 1][d + 1] += 1;diff[c + 1][b] -= 1;diff[a][d + 1] -= 1;}void build(vector<vector<int>> &m) {for (int i = 1; i < m.size(); i++)for (int j = 1; j < m[0].size(); j++)m[i][j] += m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1];}int sumRegion(vector<vector<int>> &sum, int a, int b, int c, int d) {return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];}// 时间复杂度 O(n*m)，额外空间复杂度 O(n*m)bool possibleToStamp(vector<vector<int>> &grid, int stampHeight, int stampWidth) {int n = grid.size();int m = grid[0].size();// 前缀和数组vector<vector<int>> prefixSum(n + 1, vector<int>(m + 1));for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)prefixSum[i + 1][j + 1] = grid[i][j];build(prefixSum);// 差分矩阵// 当贴邮票的时候，不再原始矩阵里贴，在差分矩阵里贴// 原始矩阵用来判断能不能贴邮票，不进行修改// 每贴一张邮票都在差分矩阵里修改vector<vector<int>> diff(n + 2, vector<int>(m + 2));// 原始矩阵中 (a,b) 左上角点，根据 stampHeight、stampWidth，算出右下角点(c,d)for (int a = 1, c = a + stampHeight - 1; c <= n; a++, c++)for (int b = 1, d = b + stampWidth - 1; d <= m; b++, d++)// 这个区域彻底都是 0 时，可以贴邮票if (sumRegion(prefixSum, a, b, c, d) == 0)add(diff, a, b, c, d);build(diff);// 检查所有的格子for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)// 原始矩阵里：grid[i][j] == 0，说明是个洞// 差分矩阵里：diff[i + 1][j + 1] == 0，说明洞上并没有邮票// 此时返回 falseif (grid[i][j] == 0 && diff[i + 1][j + 1] == 0)return false;return true;}
};
离散化技巧
LCP 74. 最强祝福力场
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:// 排序并去重int mySort(vector<long> &nums) {sort(nums.begin(), nums.end());int size = 1;for (int i = 1; i < nums.size(); i++)if (nums[i] != nums[size - 1])nums[size++] = nums[i];return size;}// 根据数值二分找下标int rank(vector<long> &nums, long v, int size) {int l = 0;int r = size - 1;int m, res = 0;while (l <= r) {m = (l + r) / 2;if (nums[m] >= v) {res = m;r = m - 1;} else {l = m + 1;}}return res + 1;}// 二维差分void add(vector<vector<int>> &diff, int a, int b, int c, int d) {diff[a][b] += 1;diff[c + 1][d + 1] += 1;diff[c + 1][b] -= 1;diff[a][d + 1] -= 1;}// 时间复杂度 O(n^2)，额外空间复杂度 O(n^2)，n 是力场的个数int fieldOfGreatestBlessing(vector<vector<int>> &forceField) {int n = forceField.size();// n 为矩形的个数，2*n 个坐标vector<long> xs(n << 1);vector<long> ys(n << 1);for (int i = 0, k = 0, p = 0; i < n; i++) {long x = forceField[i][0];long y = forceField[i][1];long r = forceField[i][2];xs[k++] = (x << 1) - r;xs[k++] = (x << 1) + r;ys[p++] = (y << 1) - r;ys[p++] = (y << 1) + r;}int size_x = mySort(xs);int size_y = mySort(ys);// n 个力场，size_x : 2 * n, size_y : 2 * nvector<vector<int>> diff(size_x + 2, vector<int>(size_y + 2));for (int i = 0, a, b, c, d; i < n; i++) {long x = forceField[i][0];long y = forceField[i][1];long r = forceField[i][2];a = rank(xs, (x << 1) - r, size_x);b = rank(ys, (y << 1) - r, size_y);c = rank(xs, (x << 1) + r, size_x);d = rank(ys, (y << 1) + r, size_y);add(diff, a, b, c, d);}int res = 0;// O(n^2)for (int i = 1; i < diff.size(); i++) {for (int j = 1; j < diff[0].size(); j++) {diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];res = max(res, diff[i][j]);}}return res;}
};
