---

---

1.题目

DP35 【模板】二维前缀和

描述

给你一个 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，分别代表这次查询的参数

输出描述：

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

示例1

输入：

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.思路

暴力解法，时间复杂度为O(n* m *q),二维前缀和时间复杂度为O(m *n)+O(q)，

• 从 [0, 0] 位置到 [i, j] 位置这⽚区域是我们处理的范围
• 注意，下表边界从1开始，方便计数, 用arr表示而我矩阵，dp 数组一般第 0 行和 第 0 列 的数据是手动初始化，从 arr矩阵到 dp 表，横纵坐标加一
• dp[i] [j] 的含义：dp[i] [j] 表⽰，从 [1, 1] 位置到 [i, j] 位置这段区域内，所有元素的累加和

• dp[i] [j] = A + B + C + D
• 将该式子替换为 dp[i] [j] =(A+C)+(A+B)-A+D
• A+C 的面积就是 dp[ i ] [ j-1 ] 的值
• A+B 的面积就是 dp[ i-1 ] [ j ] 的值
• A 的面积就是 dp[ i-1 ] [ j-1 ] 的值
• D 的面积就是 arr[ i ] [ j ] 的值

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

• 获取（x1，y1）~（x2，y2）这个区间内的数据总和 x，计算 x = s - A - B - C 的值
• 修改为x = s - (A+B) - (A+C) + A
• s 的面就是 dp[ x2 ] [ y2 ]
• A+B 的面积就是 dp[ x2 ] [ y1-1 ]
• A+C 的面积就是 dp[ x1-1 ] [ y2 ]
• A 的面积就是 dp[ x1-1 ] [ y1-1 ]

x = dp[ x2 ][ y2 ] - dp[ x2 ][ y1-1 ] - dp[ x1-1 ][ y2 ] + dp[ x1-1 ][ y1-1 ] 

3.代码

#include <iostream>
#include <vector>
using namespace std;int main() {//1.读取数据int n = 0, m = 0, q = 0, x1 = 0, y1 = 0, x2 = 0,y2 = 0; //赋初值，养成好习惯cin >> n >> m >> q;vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {cin >> arr[i][j];}}//2.预处理前缀和矩阵vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0)); //防止溢出for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i - 1][j - 1]+ arr[i][j];}}//3.使用前缀和矩阵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;}

---