前缀和算法 -- [模版]一维前缀和

2024-01-01 18:41:40

?个人主页:Lei宝啊?

愿所有美好如期而遇


目录

本题链接

输入描述

输出描述

算法分析

算法一:暴力求解

算法二:前缀和

预处理前缀和dp表

使用前缀和dp表

解题源码


我们以一道题目为例详解一维前缀和原理。?

?

本题链接

【模板】前缀和_牛客题霸_牛客网?

输入描述

首先第一行输入两个整数,n和q,n是要输入的数组的元素个数,q是要查询的次数,查询时输入l和r,代表着要查询的数组区间

比如:我们的示例:

  • n = 3,我们输入的数组元素就有三个:1 2 4
  • q = 2,我们就需要查找两次,l和r也就会更新两次,要查询的数组区间也就是[1,2] [2,3]

值得注意的是n和q都大于等于1,至于为什么要这么给,我们后面讲算法会说到。?

输出描述

返回要查询的数组区间内所有元素值的和。

算法分析

算法一:暴力求解

直接遍历数组,从给定区间开始遍历q次,我们分析一下时间复杂度:首先有q次的遍历,并且我们考虑最坏的情况,就是每次数组都是从头遍历到尾,时间复杂度就为O(q*N),按我们本题最大的q和n来看,这么干绝对是超时的。

算法二:前缀和
预处理前缀和dp表

类似于动态规划的dp表,这里的dp表每个元素都表示一个状态,由于我们的n是从1开始的,那我们的dp[1]就用来表示区间[1,1]的和,dp[1]表示区间[1,2]的和,看图更直观些:

我们可以用一个变量sum来表示和,然后通过遍历数组给dp表赋值。?

使用前缀和dp表

那么我们如何使用dp表来求取数组区间的元素和呢?

我们dp表第i个位置就表示从下标0到下标i所有元素的和,比如我们要算[2,3]区间,也就是求这个区间的元素和,就是dp[3]-dp[1],我们也就能推知一个公式:

区间和 = dp[r] - dp[l-1];

解题源码

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

int main() 
{
    int n = 0, q = 0;
    cin >> n >> q;

    vector<int> v(n+1,0);
    for(int i=1; i<v.size(); i++) cin >> v[i];

    //创建dp表,并填值
    vector<long long> dp(n+1,0);
    long long sum = 0;
    for(int i=1; i<v.size(); i++)
    {
        sum += v[i];
        dp[i] = sum;
    }

    //查询
    while(q--)
    {
        int l, r;
        cin >> l >> r;

        cout << dp[r] - dp[l-1] <<endl;           
    }
}
// 64 位输出请用 printf("%lld")

?

文章来源:https://blog.csdn.net/m0_74824254/article/details/135326684
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。