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

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

点击直接跳转到该题目

目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码

1️⃣题目描述

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

接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和。

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

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

接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

注意：

1 ≤ n , m ≤ 10001 ≤ q ≤ 1 0 5 10^{5} 105- 1 0 9 10^{9} 109 <= a[i][j] <= 1 0 9 10^{9} 1091 <= x1 <= x2 <= n1 <= y1 <= y2 <= 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; }

最后就是代码通过啦！！！