【算法小课堂】深入理解前缀和算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法小课堂】深入理解前缀和算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【算法小课堂】深入理解前缀和算法,算法小课堂,算法,动态规划

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

我们通过一个例子来理解前缀和算法的优势：

一维前缀和：

www.nowcoder.com

我们可以通过暴力的解法去解决这个问题，但是这样时间复杂度会比较高，达到O（n*q）

我们可以对暴力解法进行优化：

我们以【1,4,7,2,5,8,3,6,9】这个数组来讲解前缀和（快速求出数组中某个连续区间的元素和）这个算法

index为数组下标，至于为什么下标从一开始后面会讲！！！

【算法小课堂】深入理解前缀和算法,算法小课堂,算法,动态规划

我们提前弄一个前缀和数组dp，这个数组的元素dp【i】代表【1，i】区间内所有元素之和

【算法小课堂】深入理解前缀和算法,算法小课堂,算法,动态规划

我们在求dp的时候肯定不可以用暴力解法，不然的话时间复杂度又上去了，

dp【i】代表【1，i】区间内所有元素之和，那dp【i-1】代表【1，i-1】区间内所有元素之和

dp【i】就可以等于dp【i-1】+arr【i】

那我们再来看看题目，题目要求我们输出从l到r区间内所有元素之和

那我们可以直接输出dp【r】-dp【l-1】

#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);
    for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")