牛客每日一题之 前缀和

目录

题目介绍：

算法原理：

前缀和：

代码实现：

题目介绍：

题目链接：【模板】前缀和_牛客题霸_牛客网

算法原理：

先讲讲暴力解法每次求出数组下标r之前元素的和，再减去数组下标l-1之前元素的和，就是我们想的到的，如图：

如果只进行一次查询还好，可他要进行q次查询，n，q最大取10的5次方 最坏情况的话，每次查询都要遍历整个数组，时间复杂度为O（n*q）==10的10次方，想都不用想必定超时。

前缀和：

其实我们可以优化一下，重新创建一个新数组（我命名为dp），这个数组i下标对应的元素是arr数组（原数组）的下标i之前的元素和，如图：

这样我们利用O（n）的时间复杂度，作出这个数组后，以后的查询只需利用 dp数组中的元素来相减的到结果gentle=dp[r]-dp[i-1],所以查询q次的时间复杂度O（q），所以总体的时间复杂度为O（n）+O（q）。

我们在实现dp这个数组时，不必算每个元素都去原数组求一遍和，有更简单的算法，如图：

我们可以发现其实dp的每一个元素都等于它的前一个元素和对应下标arr数组元素的和，也就是dp[i]=dp[i-1]+arr[i],这里还需注意一个特殊情况，d[0]是没有前一个元素的哦，而且我们题目的下标是从1开始的，而我们数组默认下标是从0开始的，所以我们应该给这两个数组的第一个位置放两个无效数据0，如图：

代码实现：

C++

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

int main() {
    //输入数据
    int n,q;
    cin>>n>>q;
    vector<int> arr(n+1);
    int i=0;
    for(i=1;i<=n;i++)
    {
        int b=0;
        cin>>b;
        arr[i]=b;
    }
    //dp数组实现
    vector<long long> dp(n+1);
    for(i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+arr[i];
    }
    //进行q次查询
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
}