前缀和算法习题篇(上)-1.一维前缀和

题目描述：

解法一：暴力解法：模拟

时间复杂度是O(n*q),会超时。

解法二：前缀和解法：快速求出数组中某一个连续区间的和

快速是指O(1),前缀和思想可把时间复杂度可降到O(q)。

算法思路：

1. 先预处理出来一个前缀和数组：O(n)

• dp[i] 表示： [1, i] 区间内所有元素的和，那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和。
• 递推公式： dp[i] = dp[i - 1] + arr[i] ；

2. 使用前缀和数组，快速求出某一个区间内所有元素的和：O(q)

• 当询问的区间是 [l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1] 。

时间复杂度为O(q)+O(n).

为什么我们的下标要从1开始计数呢？

举例：当访问的区间是[0,2]时，区间内所有元素的和为dp[2]-dp[-1]，这里的dp[-1]越界。而当访问的区间是[1,2]时，区间内所有元素的和为dp[2]-dp[0],使dp[0]=0即可，不会越界。

• 为了处理边界情况
• 初始化：添加虚拟结点(辅助结点)

代码实现：

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

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

   //2.预处理出来一个前缀和数组
   vector<long long> dp(n+1);//防止溢出
   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;
}