初识算法 · 前缀和(1)

目录

前言：

一维数组的前缀和

题目解析

算法原理

算法编写

二维数组的前缀和

题目解析

算法原理

算法编写

前言：

​本文的主题是前缀和，通过两道题目讲解，一道是一维数组的模板，一道是二维数组的模板。
链接分别为：
【模板】前缀和_牛客题霸_牛客网
【模板】二维前缀和_牛客题霸_牛客网
题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

一维数组的前缀和

题目解析

题目看起来是较为复杂的，一共需要输入四个数，输入的n代表的是这个数组的长度，q代表的是查询的次数，l 和 r代表的是下标，输出的是数组arr[l] + …… + arr[r]。

那么这里就是有疑问的，题目描述的为什么是从a[1]到a[n]？而不是从arr[0]开始呢？

这里是为了防止边界，我们在算法原理部分介绍。

我们首先思考暴力解法，暴力解法无非就是模拟这个相加的过程，那么时间复杂度是查询次数 * （l - r + 1），所以最坏的情况就是l是1，r是n，所以时间复杂度就是q * n。

在这里，时间肯定是过不了的，因为题目要求：

所以q * n的话，时间复杂度是10^5，放在任何一道编程题都是过不去的。

那么我们的前缀和算法就闪亮登场了。

算法原理

这道题目我们使用的是前缀和数组，那么什么是前缀和呢？

前缀和数组，无非就是dp[i]代表的是从arr[0]一直加到arr[i]，这个数组的使用在这里已经很接近我们使用该数组的本意了。

使用该数组为了简化我们暴力遍历数组这个过程。

那么对于l r来说，我们要求的是arr[l] + …… + arr[r]，所以这个过程我们可以使用前缀和数组简化成dp[r] - dp[l - 1]，那么这个过程是O(1)的，也就是整体下来时间复杂度是q的。

但是为什么索引是从1开始的呢？这是为了处理边界情况，如果我们要求的是 0 2这个区间，那么l - 1的值就是-1，对于一个数组来说肯定是访问不了-1的，所以这道题是从1开始的。

这是一个小细节。

算法编写

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    //1.输入数据
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1, 0);
    for(int i = 1;i <= n; i++) 
        cin >> arr[i];

    //2.预处理前缀和数组
    vector<long long> dp(n + 1, 0);
    for(int i = 1; i <= n; i++)
        dp[i] = dp[i - 1] + arr[i];

    //3.使用前缀和数组
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

但是这道题目有个坑就是，如果两个整型相加可能会导致溢出的问题，所以dp数组使用的long long类型。

这是一维数组的模板，下一道题目是二维数组的模板。

二维数组的前缀和

题目解析

题目的要求和一维数组是差不多的，但是并不是从1一直加到n的，而是一个区域：

就像这样，输入的x1 y1 x2 y2是1 1  2 2，那么要求的值就是由这几个下标组成的正方形的值。

当然了，暴力解法的话，肯定是要超时的，所以我们就不予考虑了。

题目的要求我们也是基本清楚了，并且在牛客上的时候，会提示使用lld打印，所以存在溢出的风险，第二个数组就使用long long类型了。

我们就直接介绍二维数组前缀和的算法原理了。

算法原理

对于二维数组前缀和的算法原理部分，同理，我们就需要得到i j对应的区域大小了：

我们如果直接遍历的话，就和暴力解法没有什么区别，所以我们不如拆分一下这个二维数组，对于dp[i][j]来说的话，就是从1 1的位置到i j位置，我们可以划分成四个区域，A B C D，如果单独求A B C的大小并不是很好求的，所以我们不妨变动一下式子，改成A + B + A + C + D - A。

此时A + B就是dp[i - 1][j] A + C 就是等于dp[i][j - 1]，D就是arr[i][j]，A就是dp[i - 1][j - 1]。

得到dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]。

预处理前缀和数组就结束了，接下来是如何使用的问题。

给的是x1 y1 x2 y2，题目要求的值就是D。同样的，如果我们直接硬求每个区域的值，非常麻烦，所以我们不妨变化一下式子 D = A + B + C + D - (A + B) - (A + C) + A。至于为什么这样干，因为我们发现如果单独求B或者C十分麻烦，所以用来和A结合一下。

此时对于A + B + C + D，就是dp[x2][y2]，对于A + C来说，就是dp[x2][y1 - 1]，对于A + B来说，就是dp[x1 - 1][y2]，A就是dp[x1 - 1][y1 - 1]。

使用前缀和结束了，这道题目也就结束了。

算法编写

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    //1.输入数据
    int n = 0, m = 0, q = 0;
    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];

    //2.预处理前缀和数组
    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];

    //3.使用前缀和数组
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    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;
}

前缀和的模板就介绍完毕了~

感谢阅读！