浅谈前缀和 2023.9.28

\(tips:\) 文章持续更新中,欢迎关注
\(upd:\)文章从洛谷博客迁移至博客园（\(2024.1.19\)）

洛谷B3612 【深进1.例1】求区间和

题目大E：

有一个内部元素个数为\(n\)的数组\(a\),现在有m次询问,求a[l]到a[r]之间所有元素的和

朴素的做法:

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;//数据范围1e5
int a[N];//数组a
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //取消同步流 加快i/o速度
    int n; cin >> n;//读入n
    for(int i = 1; i <= n; i++) cin >> a[i];
    int m; cin >> m; //读入m
    while(m--)//循环m次
    {
        int ans = 0; 
        int l, r; cin >> l >> r;
        for(int i = l; i <= r; i++)//i从l到r
            ans += a[i];//累加a[i]
        cout << ans << '\n';//输出ans
    }

    return 0;
}

这样其实也是能AC的

但是,4.35秒的时间显然不够让人满意

简单一算复杂度\(O(m(r-l))\)
数据稍微大一点就会TLE,可以去ETOJ[oj.eriktse.com]里的模板前缀和提交相同的代码看结果
但是有没有一种方法,能够代替这种不尽人意的结果呢?

前缀和做法

我们可以新建一个数组\(p\), p[i]表示从a[1]到a[i]a数组内所有元素的和
可以得出计算公式:\(p[i] = p[i - 1] + a[i]\)
其实其中也蕴含了递推的思想

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5;
int a[N], p[N]; //创建a数组和前缀和数组
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i]; //读入数组a
    for(int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i]; //计算前缀和
    int m; cin >> m; //读入m
    while(m--)//循环m次
    {
        int l, r; cin >> l >> r;
        cout << p[r] - p[l - 1] << '\n';//从1到r减去从1到l-1,就是r~l区间的和
    }

    return 0;
}

是不是很优雅?
而同时这种代码也拥有较为优秀的时间复杂度:\(O(n)\)的计算时间,\(O(1)\)的询问复杂度

太优雅了

135ms和4s你选哪一个

总结

前缀和其实更多的是一种思想,运用前缀和思想解题才是最重要的

例题:P8772 [蓝桥杯 2022 省 A] 求和

本题其实也有朴素的做法

但是如果你使用朴素的做法,那么恭喜你荣获30分

题目大E:

根据我们小学二年级就学过的乘法分配律,我们可以得出:
\(S = a[1] * (a[2] + a[3] + ... + a[n - 1] + a[n] ) + a[2] * (a[3] + a[4] + ... + a[n]) + a[n - 1] * a[n]\)

而a[i]乘的那一个算式,就是对a[i + 1]到a[n]求和,通过前缀和可以直接求出,而不用像朴素的做法那样一个一个乘一个一个加

完整AC代码

#include <iostream>
using namespace std;
#define int long long
const int N = 2 * 1e5 + 5;
int a[N], p[N];
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//不解释了
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];//计算前缀和
    int ans = 0;
    for(int i = 1; i < n; i++)
        ans += a[i] * (p[n] - p[i]);//对a[i-1]到a[n]求和,用p[n]-p[i],最后累加
    cout << ans << '\n';//输出答案

    return 0;
}

END

好了,前缀和后面还会再讲一讲,目前就先到这里--2023/9/29 00:06

祝看到这篇文章的人rp++

END