初识算法 · 前缀和(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;
}

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


感谢阅读!

上一篇:python如何通过json以及pickle读写保存数据


下一篇:4-petalinux2018.3 摸索记录 -linux 驱动 (交叉编译)