【算法|前缀和系列No.2】牛客网 DP35 【模板】二维前缀和

个人主页：兜里有颗棉花糖
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由兜里有颗棉花糖原创
收录于专栏【手撕算法系列专栏】【牛客网刷题】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

题目描述：
给你一个 n 行 m 列的矩阵 A ，下标从1开始。

接下来有 q 次查询，每次查询输入 4 个参数 x₁ , y₁ , x₂ , y₂

请输出以 (x₁, y₁) 为左上角 , (x₂,y₂) 为右下角的子矩阵的和。

输入描述：
第一行包含三个整数n,m,q.

接下来n行，每行m个整数，代表矩阵的元素

接下来q行，每行4个整数x₁, y₁, x₂, y₂，分别代表这次查询的参数

注意：

1 ≤ n , m ≤ 1000
1 ≤ q ≤ $10^{5}$
- $10^{9}$ <= a[i][j] <= $10^{9}$
1 <= x₁ <= x₂ <= n
1 <= y₁ <= y₂ <= m

输出描述：

输出q行，每行表示查询结果。

示例：

输入：
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4

输出：
8
25
32

2️⃣题目解析

状态表示及状态转移方程：

dp[i][j] ：表示从坐标(1,1)到坐标(i,j)中所有元素的和。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];

最后输出结果：dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]

3️⃣解题代码

解题代码1：

#include<iostream>
#include<vector>
using namespace std;const int N = 1e3 + 10, M = 1e3 + 10;int main()
{int n , m , q;cin >> n >> m >> q;long long arr[N][M];vector<vector<long long>> dp(n + 1,vector<long long>(m + 1));for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> arr[i][j];dp[i][j] = dp[i][j - 1] + arr[i][j];}}while(q--){int x1,y1,x2,y2;long long ret = 0;cin >> x1 >> y1 >> x2 >> y2;for(int i = x1;i <= x2;i++){ret += (dp[i][y2] - dp[i][y1 - 1]);}cout << ret << endl;}return 0;
}

解题代码2：

#include<iostream>
#include<vector>
using namespace std;
int main()
{int n,m,q;cin >> n >> m >> q;vector<vector<int>> arr(n + 1,vector<int>(m + 1));for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++)cin >> arr[i][j];// 创建前缀和矩阵vector<vector<long long>> dp(n + 1,vector<long long>(m + 1));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] + arr[i][j] - dp[i - 1][j - 1];// 使用前缀和矩阵int x1,y1,x2,y2;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}