当前位置：首页 > news >正文

前缀和算法 cpp

news 2026/5/12 14:00:23

4. 前缀和

前缀和与差分的核心思想就是预处理, 可以在暴力枚举的过程中, 可以快速给出查询结果, 从而优化结果, 从而优化时间复杂度

是经典的用空间替换时间的做法

4.1 一维前缀和

[牛客网]【模板】前缀和

思路:

前缀和 -> 快速求出数组中, 某一段的区间和
O(1)

先预处理出来一个前缀和数组
f[i]表示: 区间[1, i]中, 所有元素的和
f[i] = f[i-1] + a[i]
利用前缀和数组求和

代码:

暴力解法 -> 模拟

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intm,n;inta[N];intl,r;intmain(){cin>>n>>m;for(inti=0;i<n;i++)cin>>a[i];while(m--){cin>>l>>r;intsum=0;for(inti=l-1;i<r;i++){sum+=a[i];}cout<<sum<<endl;}return0;}

部分测试用例会超时

前缀和 -> 快速求出数组中, 某一段的区间和

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intm,n;longlonga[N];intl,r;longlongf[N];//前缀和数组intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)f[i]=f[i-1]+a[i];while(m--){cin>>l>>r;cout<<f[r]-f[l-1]<<endl;}return0;}

4.2 最大子段和

[!洛谷]
P1115 最大子段和
P1115 最大子段和 - 洛谷
题目描述
给出一个长度为n nn的序列a aa，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度n nn。
第二行有n nn个整数，第i ii个整数表示序列的第i ii个数字a i a_iai。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
7 2 -4 3 -1 2 -4 3
输出 #1
4
说明/提示
样例 1 解释
选取[ 3 , 5 ] [3, 5][3,5]子段{ 3 , − 1 , 2 } \{3, -1, 2\}{3,−1,2}，其和为4 44。
数据规模与约定
对于40 % 40\%40%的数据，保证n ≤ 2 × 10 3 n \leq 2 \times 10^3n≤2×103。
对于100 % 100\%100%的数据，保证1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^51≤n≤2×105，− 10 4 ≤ a i ≤ 10 4 -10^4 \leq a_i \leq 10^4−104≤ai≤104。
2026/01/21：增加一组 hack 数据。

思路:

利用前缀和

找以a[i]为结尾的所有子区间中最大的子段和
用f[i]减去[1, i-1]中所有前缀和最小值 = 以a[i]为结尾最大值

代码:

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+10;intn;LL f[N];//前缀和数组intmain(){cin>>n;for(inti=1;i<=n;i++){LL x;cin>>x;f[i]=f[i-1]+x;}LL ret=-1e20;LL prevmin=0;for(inti=1;i<=n;i++){ret=max(ret,f[i]-prevmin);prevmin=min(prevmin,f[i]);}cout<<ret<<endl;return0;}