前缀和算法详解（附C++代码示例）_c++前缀和算法

一.什么是前缀和？

       前缀和是一种常用的算法，对于一维数组，S[i]=S[i-1]+a[i]，其中S数组即为前缀和数组，a数组为原数组，S[i]即表示a数组下标为0-i的值的和。

二.前缀和有什么用？

       前缀和用于高效计算数组中某个区间内元素的和，比如我们要求a数组中下标从i到j的值的和，那么当我们有前缀和数组时，只需要转化为求S[j]-S[i-1],否则，我们需要遍历i - j 。当这样的查询次数愈发增多时，就越显示出前缀和数组的高效。

三.示例

        以下代码用于给定一个长度为n的数组a，每一次查询需要得出数组a中下标从l到r的值，共需求出q次查询的结果（时间复杂度：O（n）（假设n>q））。

#include <iostream>
using namespace std;
 
const int N=1e5+5;
 
int S[N],a[N];
 
int n,q;//n表示数组实际长度，q表示查询次数。
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        S[i]=S[i-1]+a[i]; 
    }
 
    cin>>q;
    int l,r;
    
    while(q--)
    {
        cin>>l>>r;
        cout<<S[r]-S[l-1]<<endl;
    }
}