【算法入门】前缀和

什么是前缀和？

1.一维前缀和：

有一个一维数组a和该数组的一维前缀和数组 b，则 a和 b
满足以下关系：
b0=a0,b1=a1+a0,…,bn=a0+a1+…+an;

2.如何得到前缀和

不难发现这就是高中的数列，则bn=bn-1+an；
代码实现

for(int i=0;i<n;i++)
{
    if(i==0) 
    b[i]=a[i];
    else 
    b[i]=b[i-1]+a[i];
}

3.前缀和的运用

前缀和主要用于降低时间复杂度，举个例子：给定 n个整数，然后进行q次询问，每次询问求一个区间[L,R]值的和。
如果用暴力写法，那每次询问都需要从区间左端点循环到区间右端点求和，时间复杂度较大。
这时候就可以用一维前缀和。
则 S=a[R]-a[L-1]，每次询问可直接输出答案，这样时间复杂度就降到了O(n+q）。

4. 经典题

问题描述:

给定一个长度为n的数组a*1,a2,…an.

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

对于每个询问, 请输出al+al+1+…+a*r

输入描述:

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

第二行包含n个整数, 表示a1,a2,…a**n.

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

1≤n,q≤105
?109≤a[i]≤109
1≤l≤r≤n

输出描述:

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

解题思路

1.分析问题,此题其实就是求数列前n项和的变式

2.由数列的性质我们可以得到:

Sn-Sn-1=an n>=2,

S1=a1;

且al+al+1+…+ar=S[r]-S[l-1].

即输出S[r]-S[l-1].

3.遍历即可

代码实现

#include <iostream>
using namespace std;
const int N =1e5+5;

int main() {
    long long arr[N];
    int n, q;
    cin>>n>>q;
    for(int i1;i<=n;i++)
    
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++)
    {
        arr[i]+=arr[i-1];      
    }
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<arr[r]-arr[l-1]<<endl;
    }
    return 0;
}