【算法挨揍日记】day13—— DP34 【模板】前缀和、DP35 【模板】二维前缀和

Dear 丶 2024-02-25 02:32 32阅读 0赞

![570b75578b874e4bb492c02f62a95442.png][]

## DP34 【模板】前缀和 ##

[【模板】前缀和\_牛客题霸\_牛客网][Link 1]

### 题目描述： ###

给定一个长度为n的数组. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出

输入描述:

第一行包含两个整数n和q.第二行包含n个整数, 表示.接下来q行,每行包含两个整数 l和r.

输出描述:

输出q行,每行代表一次查询的结果.

示例1

输入

3 2  
1 2 4  
1 2  
2 3

输出

3  
6

### 解题思路： ###

> 我们可以可以通过暴力的解法去解决这个问题，但是这样时间复杂度会比较高，达到O（n\*q）
> 
> 我们可以对暴力解法进行优化：
> 
> 我们以【1,4,7,2,5,8,3,6,9】这个数组来讲解前缀和（快速求出数组中某个连续区间的元素和）这个算法
> 
> index为数组下标，至于为什么下标从一开始后面会讲！！！
> 
> ![3dd1dd1c08a54ce496e9424a7d92abf6.png][]
> 
> 我们提前弄一个前缀和数组dp，这个数组的元素dp【i】代表【1，i】区间内所有元素之和
> 
> ![5ca9c6b53ffc4153baf5f96a0cfec4ab.png][]
> 
> 我们在求dp的时候肯定不可以用暴力解法，不然的话时间复杂度又上去了，
> 
> dp【i】代表 【1，i】区间内所有元素之和，那dp【i-1】代表 【1，i-1】区间内所有元素之和
> 
>  *  dp【i】就可以等于dp【i-1】+arr【i】
> 
> 那我们再来看看题目，题目要求我们输出从l到r区间内所有元素之和
> 
> 那我们可以直接输出dp【r】-dp【l-1】
> 
>  *  这里我们把下标设为1开始，是因为我们的dp在算的时候会用到i-1的位置，如果i从0开始就会出现越界的情况

### 解题代码： ###

#include <iostream>
    #include<vector>
    using namespace std;
    int main() {
        int n,q;
        cin>>n>>q;
        vector<int> arr(n+1);
        for(int i=1;i<=n;i++) cin>>arr[i];
        vector<long long> dp(n+1);
        for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];
        while(q--)
        {
            int l,r;
            cin>>l>>r;
            cout<<dp[r]-dp[l-1]<<endl;
        }
        return 0;
    }
    // 64 位输出请用 printf("%lld")

--------------------

## DP35 【模板】二维前缀和 ##

### 题目描述： ###

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

输入描述：

第一行包含三个整数n,m,q.  
  
接下来n行，每行m个整数，代表矩阵的元素  
  
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

![a70f6bf108cf4170a9abe2e3364d8154.png][]

### 解题思路： ###

> 首先如果我们使用暴力解法时间复杂度，直接就是O(n\*m\*q），我们可以对其使用前缀和算法优化
> 
> 我们可以创建一个（n+1）\*（m+1）的的数组arr和（n+1）\*（m+1）的的前缀和数组dp
> 
>  *  这里数组坐标加一也是为了防止越界的情况
> 
> dp【i】【j】代表从（1,1）~（i，j）这个区间内所有元素之和
> 
> 我们如何快速求出dp【i】【j】的值呢？以下面这个数组为例，假设我们要求的是dp【3】【3】
> 
> ![141f5c46b8364e78a34e1d8bf50c5815.png][]
> 
> 我们先来观察一个通用图：我们要求多少A+B+C+D之和
> 
> ![1de5c70771044623a7a4717ddbd48339.png][]
> 
> A+B+C+D=（A+B）+（A+C）+D-A，括号内的是一个整体
> 
> 我们可以结合下标的关系推导进一步的关系
> 
> ![54e30c597616423f9e37bd89465fa4c6.png][]
> 
> A+B+C+D=（A+B）+（A+C）+D-A
> 
> =dp【i-1】【j】+dp【i】【j-1】+arr【i】【j】-dp【i-1】【j-1】
> 
> 这样我们就求出来了dp的每一个数了，回到题目上，题目要求我们输出（x1,y1)~(x2,y2)这个区间内的所有元素之和，假设让我们输出是是这个区间
> 
> ![1c6a9936596f472984712c50fbe3659a.png][]
> 
>  *  D=（A+B+C+D）-（A+B）-（A+C）+A
> 
> ![9dc7395132334a5f92267dcca02ee6e6.png][]
> 
> D=（A+B+C+D）-（A+B）-（A+C）+A
> 
> = dp【x2】【y2】-dp【x1-1】【y2】-dp【x2】【y1-1】+dp【x1-1】【y1-1】
> 
> 为了防止越界，我们开辟数组也要多开一行一列
> 
> ![7317fa5965034993a44137f57752e88d.png][]

### 解题代码： ###

#include <iostream>
    #include<vector>
    using namespace std;
    int main() {
        int n,m,q;
        cin>>n>>m>>q;
        int arr[n+1][m+1];
        long long dp[n+1][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-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];
            }
        }
        while(q--)
        {
            int x1,x2,y1,y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;
        }
        return 0;
    }
    // 64 位输出请用 printf("%lld")

![126a544748014d76ba492ebf36606390.gif][]

[570b75578b874e4bb492c02f62a95442.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/5f78205b19064c86b91e87fa99470f06.png
[Link 1]: https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196#:~:text=%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA,%E5%89%8D%E7%BC%80%E5%92%8C
[3dd1dd1c08a54ce496e9424a7d92abf6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/28537659489349fcbefa5e7c6a5d286f.png
[5ca9c6b53ffc4153baf5f96a0cfec4ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/c802b0197ff64ef19749599d1f2d00fe.png
[a70f6bf108cf4170a9abe2e3364d8154.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/fa4ff1c1d14547d08fd8a4eea802f5ad.png
[141f5c46b8364e78a34e1d8bf50c5815.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/fb8b9ecfb7aa41d8b177b2fff82516a4.png
[1de5c70771044623a7a4717ddbd48339.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/86ff5ec509314f1889e23027b90bcd80.png
[54e30c597616423f9e37bd89465fa4c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/e771c949c6ad402ba01a846ad43c4f45.png
[1c6a9936596f472984712c50fbe3659a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/b2145c24d7c7488b9c5a4be78295baa6.png
[9dc7395132334a5f92267dcca02ee6e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/e7d722bdf7074c4fad801f3b0f4db83e.png
[7317fa5965034993a44137f57752e88d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/cf445c0b1b8d4e7ca9a46fbecfea4684.png
[126a544748014d76ba492ebf36606390.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/1109fb5d45a243ffb4b2f65037236f1d.png