【算法入门】前缀和

发布时间:2024年01月17日

什么是前缀和?

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≤lrn

输出描述:

输出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;
}


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