新生培训之前缀和与差分 ----二维前缀和篇

用户11956880

发布于 2025-12-18 18:22:36

640

上一个讲的是一维前缀和，这篇说二维的

二维前缀和

二维其实也没差别多少，一维前缀和就是从0，位置到n位置的前n项和

而二维前缀和就是从(0,0)位置到(i,j)位置的这个面积的和，就像下图画的那样，如果prefix[2][2]就是这个矩形里的数的和

同样的和一维一样他也有自己的递推公式

1 2 3 4 5 6 7 8 9

下面就是对应的前缀和

1 3 6 5 12 21 12 27 45

之前一维我们只用prefix[i]=prefix[i-1]+arr[i]就行，就可以依次得到整个数组的前缀和

现在二维的话，通过上面我写的图可以知道，（sum我就直接换成prefix了哈）

递推公式

prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j]

子矩阵和查询公式

我们得到了二维前缀和之后，当然就要像上一篇一样去思考他能干啥，非常显眼的作用依旧是我们能得到一个区间和

要计算从 [x1,y1] 到 [x2,y2] 的子矩阵和：

sum(x1,y1,x2,y2) = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

我说一下这个是什么意思，就比如下面这个图，我想得到红色部分的和，那就需要用蓝色区域（x2，y2）的前缀和减去两个绿色区域的前缀和，也就是（x2，y1-1）的前缀和以及（x1-1，y2）的前缀和，通过图中我们还发现紫色区域是我们多减的一个区域，所以我们再加上这个区域（也就是（x1-1，y1-1）的前缀和）

需要注意的是我们在构造前缀和数组时候，如果从第0行，或者第0列开始那我们还需要特判一下，防止数组越界，那我们可以直接将这一圈都设为0，这样我们之间加0也就相当于什么也没加了，也就不需要特判了

看一下代码就行

#include<bits/stdc++.h>
using namespace std;
int arr[1000][1000];
int prefix[1010][1010];
int n,m;
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	  for(int j=1;j<=m;j++){
	  	cin>>arr[i][j];
	  	//左+上+自己-左上
		//先求得前缀和数组 
	  	prefix[i][j]=prefix[i][j-1]+prefix[i-1][j]+arr[i][j]-prefix[i-1][j-1];
	  }
	}
	int a,b,c,d;//求a,b到c,d范围的和
	int t=10;
	while(t--){
		cin>>a>>b>>c>>d;
		cout<<prefix[c][d]-prefix[c][b-1]-prefix[a-1][d]+prefix[a-1][b-1]<<endl;
	} 
}

好知识点也就这了，去写题练习

1139. 最大的以 1 为边界的正方形

https://leetcode.cn/problems/largest-1-bordered-square/

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1

思路：这个是中间可以不是1，只有边的部分都是1所以我们就可以灭磁循环判断一个正方形减去里面内层正方形，得到周长，看看周长是不是都是1就行了，我下面就是没读题以为还是这，看了一个小时没找出来我错哪了，服了

class Solution {
public:
    int prefix[110][110];
    int sum(int a,int b,int c,int d){
        return prefix[c][d]-prefix[a-1][d]-prefix[c][b-1]+prefix[a-1][b-1];
    }
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                prefix[i+1][j+1]=prefix[i][j+1]+prefix[i+1][j]-prefix[i][j]+grid[i][j];
            }
        }
        if(sum(1,1,n,m)==0)return 0;
        int ans=1;
        for(int a=1;a<=n;a++){
            for(int b=1;b<=m;b++){
                for(int c=a+ans,d=b+ans,k=ans+1;c<=n&&d<=m;c++,d++,k++){
                    if(sum(a,b,c,d)-sum(a+1,b+1,c-1,d-1)==(k-1)<<2){
                        ans=k;
                    }
                }
            }
        }
        return ans*ans;
    }
};

P1387 最大正方形

P1387 最大正方形 - 洛谷

题目描述

在一个 n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。

保证矩阵里有至少一个 1。

输入格式

输入文件第一行为两个整数 n,m(1≤n,m≤100)，接下来 n 行，每行 m 个数字，用空格隔开，0 或 1。

输出格式

一个整数，最大正方形的边长。

输入输出样例

输入 #1复制

输出 #1复制

思路：

暴力方法就是遍历所有的坐标然后往下延伸正方形，然后就看最多能延伸多少就行，我们可以用一个ans来代表我们找到的最大正方形边长，这样也能保证剪枝，我们只找每个坐标往下延伸ans长度的正方形，这样就完成了剪枝，看代码

#include<bits/stdc++.h>
using namespace std;
int n,m,arr[110][110],prefix[110][110];
int get_sum(int a,int b,int c,int d){
	return prefix[c][d]-prefix[a-1][d]-prefix[c][b-1]+prefix[a-1][b-1];
}
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	    cin>>n>>m;
	    for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>arr[i][j];
				prefix[i][j]=prefix[i][j-1]+prefix[i-1][j]+arr[i][j]-prefix[i-1][j-1];
			}
		}
		if(get_sum(1,1,n,m)==0){
			cout<<0;
			return 0;
		}
		int ans=1;
		for(int a=1;a<=n;a++){
			for(int b=1;b<=m;b++){
				//用一个ans可以进行剪枝，ans就是向下延伸的最大正方形的边长 
				for(int c=a+ans,d=b+ans,k=ans+1;c<=n&&d<=m;c++,d++,k++){
					if(get_sum(a,b,c,d)==k*k){
						ans=k;
					}
				}
			}
		}
		cout<<ans;
		
}

思路：还有个动态规划做法，这个比较简单

dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;这个递推公式其实不是很好想的

这个dp的含义是，以i，j为正方形右下角的正方形最大边长，我们可以思考一下，多一个i，j这个角，怎样能构成一个正方形，当然是他的正上方，左边和左上，我们找到最小的一个这样才能构成正方形，看代码吧，这个之后画图好理解

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[110][110],ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int a;
			cin>>a;
			dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans;
}

1364: 子矩阵的和

P1364 - 子矩阵的和 - HAUEOJ

题目描述

给定一个 n 行 m 列的二维数组 num，有 q 次询问，对于每次询问，给定两个坐标 P1(x1, y1),P2(x2, y2)，求以 P1 为左上角，P2 为右下加的子矩阵的元素之和。

输入

第一行，三个整数 n,m,q

接下来 n 行 m 列，输入 num[i]

接下来 q 行，每行四个整数 x1, y1, x2, y2

输出

共 q 行，每行输出一个整数

样例输入

复制

样例输出

复制

6
10

提示

10 <= n,m, x1 <= x2, y1 <= y2 <= 500 10 <= q <= 20000

这个是咱oj平台上的，也就是个模板题

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int arr[510][510];
int prefix[510][510];
int sum(int a,int b,int c,int d){
	return prefix[c][d]-prefix[a-1][d]-prefix[c][b-1]+prefix[a-1][b-1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
			prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+arr[i][j];
		}
	}
	while(q--){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		cout<<sum(x1,y1,x2,y2)<<endl;
	}
}

P2004 领地选择

题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 C×C 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 N,M,C，表示地图的宽和长以及首都的边长。

接下来 N 行每行 M 个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数 X,Y，表示首都左上角的坐标。

输入输出样例

输入 #1复制

输出 #1复制

1 2

说明/提示

对于 60% 的数据，N,M≤50。

对于 90% 的数据，N,M≤300。

对于 100% 的数据，1≤N,M≤103，1≤C≤min(N,M)。每块地价值的绝对值不超过 32767。

这题和上面的最大正方形其实差不多

#include<bits/stdc++.h>
using namespace std;
int arr[1010][1010],prefix[1010][1010];
int n,m,c;
int sum(int a,int b,int c,int d){
	return prefix[c][d]-prefix[a-1][d]-prefix[c][b-1]+prefix[a-1][b-1];
}
int main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
			prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+arr[i][j];
		}
	}
	int x,y,ans=INT_MIN;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(sum(i,j,i+c-1,j+c-1)>ans&&(i+c-1)<=n&&(j+c-1)<=m){
				ans=sum(i,j,i+c-1,j+c-1);
				x=i,y=j;
			}
		}
	}
	cout<<x<<' '<<y;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除

数组