一维前缀和可以简单理解为一个数组的前n项和,二维前缀和可理解为二维矩阵每个元素的总和

由上图知sum(i+1,j+1)=sum(i+1,j)+sum(i,j+1)-sum(i,j)+a(i,j);二维前缀和就是这么算的 

    int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];}}

 其中a是原数组,b是二维前缀和数组.

应用就是快速求取子矩阵的和

由推导二维前缀和的式子可知左上角顶点为(x1,y1),右下角为(x2,y2)的子矩阵的值为

sum(x2,y2)-sum(x2,y1)-sum(x1,y2)+sum(x1,y1).

应用:最大正方形

 枚举边长为1,到min(n,m)的正方形,如果找到了边长为l的正方形,就接着找是否有边长为l+1的正方形,直到找到边长最长的l

#include <algorithm>
#include <iostream>
using namespace std;
int a[103][103];
int b[103][103];  // 前缀和数组，相当于上文的 sum[]int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];b[i][j] =b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + a[i][j];  // 求前缀和}}int ans = 0;int l = 1;while (l <= min(n, m)) {  // 判断条件for (int i = l; i <= n; i++) {for (int j = l; j <= m; j++) {if (b[i][j] - b[i - l][j] - b[i][j - l] + b[i - l][j - l] == l * l){ans = max(ans, l);  // 在这里统计答案break;}}}l++;}cout << ans << endl;return 0;
}