什么是二维前缀和？

原文链接：https://blog.csdn.net/qq_34990731/article/details/82807870

前缀和，顾名思义就是第几个数之前的数的和，我们用DP来预处理，定义状态DP[i]表示到第i个数（包括它）为止前面所有数的和，从而得到状态转移方程DP[i]=DP[i-1]+num[i]，num[i]表示数组中第i个数，这样要计算闭区间i,j(闭区间就是指i<=x<=j，x就是区间里的数)的和就是DP[j]-DP[i-1].如下图：

下面我们讲一下什么是二维前缀和，建立在一维前缀和之上，我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和，我们还是用DP来预处理，状态和一维前缀和差不多，只不过我们多加了一维，DP[i][j]表示（1,1）这个点与（i，j）这个点两个点分别为左上角和右下角所组成的矩阵内的数的和，好好想一下状态转移方程 DP[i][j]=DP[i-1][j]+DP[i][j-1]-DP[i-1][j-1]+map[i][j]，,怎么来的呢？我们画一下图就知道了。

这张图就知道了（i，j）可以由（i-1，j）和（i,j-1）两块构成，不过要注意两个点，1、有一块矩阵我们重复加了，也就是（i-1，j-1）这一块，所以我们要减去它。2、我们这个矩阵是不完整的，由图可知我们还有一块深蓝色的没有加，也就是（i，j）这一点，所以我们要再加上map[i][j]也就是题目给出的矩阵中这一格的数。

这样我们就预处理完了，现在讲一下怎么通过我们的预处理从而快速地得出我们想要的任意子矩阵中的和，我们定义（x1，y1）为我们想要子矩阵的左上角，（x2，y2）为我们想要子矩阵的右下角，然后我们画图想一想。

我们可以通过DP[x2][y2]来计算，我们通过图可以发现这个距离我们要的还差红色的部分看看怎么表示红色部分？我们可以分割成两块，分别是DP[x1][y2]和DP[x2][y1]我们发现有一块重复减了，所以我们再加上它即DP[x1][y1]，有一点注意，因为画图和定义原因我们发现边界好像不对，我们来看看，我们定义的状态是整个矩阵包括边的和，而我们要求的也是要包括边的，所以我们要再改一下，把DP[x1][y2]和DP[x2][y1]和DP[x1][y1]分别改成DP[x1-1][y2]和DP[x2][y1-1]和DP[x1-1][y1-1]这样一减我们就可以得到自己想要的答案，整理可得公式，DP[x2][y2]-DP[x1-1][y2]-DP[x2][y1-1]+DP[x1-1][y1-1]这样我们就可以做到O（1）之内查询.

#include<iostream>
#include<cstring>
using namespace std;
int dp[2000][2000],map[2000][2000];
int main()
{
	int m,n,k;//所给的矩阵是n*m的,有k组查询 
	cin >>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >>map[i][j];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)//预处理一波 
		for(int j=1;j<=m;j++)
			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
	for(int i=1;i<=k;i++)//接受查询 
	{
		int x1,x2,y1,y2;
		cin >>x1>>y1>>x2>>y2;
		cout <<(dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1])<<endl;//O（1）查询 
	}
	return 0;
} 

例题：

1292.Maximum Side Length of a Square with Sum Less than or Equal to Threshold

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

题解：https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/solution/qing-xi-tu-jie-mo-neng-de-qian-zhui-he-by-hlxing/

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 Output: 2 Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 Output: 2

Constraints:

1 <= m, n <= 300 m == mat.length n == mat[i].length 0 <= mat[i][j] <= 10000 0 <= threshold <= 10^5

解法一：前缀和

思路：

遍历所有可能的正方形区域，具体的算法流程是：

1.考虑正方形的边长从 1 到 Min(M,N)（M 为矩阵长度，N 为矩阵宽度）

2.考虑正方形右下角的坐标从 (0, 0) 到 (M, N)

3.判断正方形是否存在（可能会超出边界，通过左上角坐标判断），如果存在则验证该正方形区域的元素总和。

下面引入二维前缀和的计算方法，通过预处理可以在 O(1) 时间内计算出一块区域内元素的总和。

首先是预处理，在 O(N^2) 时间内计算出二维前缀和 dp[i][j]：从 (0, 0) 到 (i, j) 内元素的总和。

已知 dp[i][j] 必定包含一个元素 mat[i][j]，假设我们已经计算出部分前缀和 dp[x][y]（x < i 且 y < j），那么 dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]。

预处理完二维前缀和，我们可以逆向这个过程，计算出某一块特定区域内元素总和： dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int k = 1; k <= Math.min(m, n); k++) {
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i - k < 0 || j - k < 0) {
                        continue;
                    }
                    int tmp = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k];
                    if (tmp <= threshold) {
                        ans = Math.max(ans, k);
                    }
                }
            }
        }
        return ans;
    }
}

解法二 前缀和 + 二分 思路 查找的正方形的边长越长，其计算出来的元素总和越大。

我们可以二分正方形的边长，在满足阈值条件下尽可能地扩大正方形的边长，其等价于在升序数组中查找一个小于等于 k 的最大元素。

class Solution {
    int m, n;
    int[][] dp;
    public int maxSideLength(int[][] mat, int threshold) {
        m = mat.length;
        n = mat[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        int ans=0;
		int left=0,right=Math.min(m,n);
		while(left<=right) {
			int mid=left+(right-left)/2;
			if(help(mid,threshold)) {
				left=mid+1;
				ans=mid;
			}else {
				right=mid-1;
			}
		}
		return ans;
    }
    
    public boolean help(int k, int threshold) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i - k < 0 || j - k < 0) {
                    continue;
                }
                if (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
}