#创作计划#前缀和精讲

‮༺དༀ༒∞░∞༒ༀཌ༻

2025-08-19 17:01:14

发布于：浙江

38阅读

0回复

0点赞

@AC君，因为某些原因本帖写的比前两篇差一点，看看能不能加精
本帖主讲前缀和。
直接开始，话不多说：

前缀和的基本概念：

前缀和算法它主要是用来求区间和的。比如说求从 $a_i$ 到 $a_j$ 之间所有的元素总和。记得某大佬说过一句话（忘了在哪了,好像是帅童说的，如有意见可删）：

诶这不是一个for循环就解决了吗？
我去咋全超时了？

这里的for循环是指直接暴力求区间和，前缀和算法也是需要for循环的。
前缀和就是通过构建前缀和数组来使查询时间复杂度为 $O(1)$ 的算法。
拿个题目来举例：
这道题我们可以明显看出数据范围高达 $10^5$ ，而暴力破解的时间复杂度约为 $O(nm)$ ，单次查询时间复杂度约为 $O(n)$ ，正常情况下绝对TLE，只不过神奇的是这题暴力居然能过。
先给出暴力代码： $\color{white}恭喜你找到了本帖的彩蛋：本帖写的很烂，欢迎白嫖$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

signed main(){
    int a,b;
    cin >> a >> b;
    int sz[1000005]={};
    int num=0;cin >> sz[1];
    for(int i=2;i<=a;i++){
        cin >> sz[i];
       
    }for(int i=1;i<=b;i++){ 
        int l,r;
        cin >> l >> r;
        int num=0;
        for(int j=l;j<=r;j++)num+=sz[j];
        cout << num << endl;
    } 
    return 0; 
}

可以看出数据但凡强一点他就TLE了。所以我们要优化这段代码。考虑使用前缀和。

前缀和讲解：

先来看看直接查询：
假设数组是 $1,2, 3 ,4 ,5$ ，有3轮查询，分别下标（从1开始）为：

$1,5$

$2,4$

$3,5$

那么手动查询的过程就是（这里的图片就一笔带过了，不做说明）：

可以看出我们每一次查询都进行了一个从 $l$ 到 $r$ 的一次 for 循环，不难发现，代码的时间复杂度极高。所以我们使用前缀和来优化该代码：
还是上边的样例，首先我们构建前缀和数组：

@AAA逃离森林湖的蔡锡龙批发提供的图片：

这里可以发现，当你想要查询一段区间的总和时，例如样例2的 $2,4$ 。我们只需要用区间为 $1 , 4$ 的数字总和减去区间为 $1 , 1$ 的数字总和，就可以得到。而我们构建了前缀和数组，区间 $1 , 4$ 的区间和其实就是 $a_4$ ，而区间为 $1 , 1$ 的数字总和就是 $a_1$ 。所以我们只需要用 $a_4$ 的值减去 $a_1$ 的值即可。以此类推，如果我们需要查询区间 $n , m$ 的总和，我们只需要使用前缀和数组中的 $a_m$ 减去 $a_{n-1}$ 即可。代码实现就是 a[m]-a[n-1] 。

代码分析：

首先构建前缀和数组，这里把他混在输入中了.由于这里没有什么多余的操作，所以直接覆盖在原数组上即可。注意需要提前渲染一下 $a_0$ 为 0 或者提前输入 $a_1$ ：

cin >> sz[1];
for(int i=2;i<=a;i++){
    cin >> sz[i];
    sz[i]+=sz[i-1];
}

之后循环输入查询的左区间，右区间：

for(int i=1;i<=b;i++){ 
    int l,r;
    cin >> l >> r;
}

输出的话按照上边的公式，在这里就是 sz[r]-sz[l-1] ：

cout << sz[r]-sz[l-1] << endl;

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int abb[10000005];
signed main(){
    int a,b;
    cin >> a >> b;
    int sz[1000005]={};
    cin >> sz[1];
    for(int i=2;i<=a;i++){
        cin >> sz[i];
        sz[i]+=sz[i-1];
    }for(int i=1;i<=b;i++){ 
        int l,r;
        cin >> l >> r;
        cout << sz[r]-sz[l-1] << endl;
    } 
    return 0; 
}