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

╰半橙微兮° 2024-04-27 06:37 66阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[牛客网刷题][Link 3]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][503fbf94852e4752a15da4b418a9909c.png]

[点击直接跳转到该题目][Link 4]

#### 目录 ####

*  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 ≤ 1000
 *  1 ≤ q ≤  1 0 5 10^\{5\} 105
 *  \- 1 0 9 10^\{9\} 109 <= a\[i\]\[j\] <=  1 0 9 10^\{9\} 109
 *  1 <= x1 <= x2 <= n
 *  1 <= 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;
    }

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

![在这里插入图片描述][6a96dc49e0f043c8bb8b6c1ae026b77a.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[Link 3]: https://blog.csdn.net/m0_74352571/category_12275139.html?spm=1001.2014.3001.5482
[503fbf94852e4752a15da4b418a9909c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6b7d0757bdfd4a078751448e5eb35d1f.png
[Link 4]: https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=/exam/oj
[6a96dc49e0f043c8bb8b6c1ae026b77a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/33e8361ad7a7403e8df2dd7ec32a00d9.png