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

2023-11-23 09:36

文章标签 模板前缀 dp34

本文主要是介绍前缀和——DP34 【模板】前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

文章目录

🍋1. 题目
🍈2. 算法原理
🍈3. 代码实现

🍋1. 题目

题目链接：【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

描述

给定一个长度为n的数组a₁,a₂,…a_n.

接下来有q次查询, 每次查询有两个参数l, r.

对于每个询问, 请输出a_l + a_l+1 + … + a_r

输入描述：

第一行包含两个整数n和q.

第二行包含n个整数, 表示a₁,a₂,…a_n.

接下来q行,每行包含两个整数 l和r.

1≤n,q≤105

−109 ≤ a[i] ≤ 109

1≤l≤r≤n

输出描述：

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

示例1

输入：

输出：

3
6

🍈2. 算法原理

解法一：暴力模拟

求哪段区间的和，我们就从指定初始位置一直加到指定结束位置，每次都是在遍历数组，询问q次，每次询问的复杂度为O(n)，所以时间复杂度总共就是O(n*q)，该题数据量十分庞大，n和q的范围都是[1,10⁵]，合起来就是10¹⁰，这肯定会超时

解法二：前缀和

前缀和思想就是快速求出数组中某一个连续区间的和，一共分为2步：

预处理出一个前缀和数组dp（原数组和dp数组下标都是从1开始），dp[i]表示[1,i]区间内所以元素的和
使用前缀和数组
如果要求区间[l,r]，直接拿dp[r] - dp[l-1]即可

这里预处理一个前缀和的数组，需要的时候直接拿值即可，这个时间复杂度为O(1)，预处理前缀和数组的复杂度为O(n)，所以该方法的复杂度为O(n)+O(q)

细节问题：

这里我们数组的下标不是从0开始，而是从1开始的。

因为这里有个边界问题，如果从0开始，例如求区间[0,3]的结果时，那么我们算出来的就是dp[3]-dp[-1]，那么这里就还需要在进行判断一下；如果从1开始，则不需要考虑这个情况，所以默认下标0处的值为0，属于一个辅助节点。

🍈3. 代码实现

#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);  //long long防止溢出for(int i=1;i<=n;i++)   dp[i] = dp[i-1]+arr[i];int l = 0;int r = 0;while(q--){cin>>l>>r;cout<< dp[r]-dp[l-1]<<endl;}return 0;
}