前缀和算法 cpp

4. 前缀和前缀和与差分的核心思想就是预处理, 可以在暴力枚举的过程中, 可以快速给出查询结果, 从而优化结果, 从而优化时间复杂度是经典的用空间替换时间的做法4.1 一维前缀和[牛客网]【模板】前缀和思路:前缀和 - 快速求出数组中, 某一段的区间和O(1)先预处理出来一个前缀和数组f[i]表示: 区间[1, i]中, 所有元素的和f[i] f[i-1] a[i]利用前缀和数组求和代码:暴力解法 - 模拟#includebits/stdc.husingnamespacestd;constintN1e610;intm,n;inta[N];intl,r;intmain(){cinnm;for(inti0;in;i)cina[i];while(m--){cinlr;intsum0;for(intil-1;ir;i){suma[i];}coutsumendl;}return0;}部分测试用例会超时前缀和 - 快速求出数组中, 某一段的区间和#includebits/stdc.husingnamespacestd;constintN1e610;intm,n;longlonga[N];intl,r;longlongf[N];//前缀和数组intmain(){cinnm;for(inti1;in;i)cina[i];for(inti1;in;i)f[i]f[i-1]a[i];while(m--){cinlr;coutf[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输入 #17 2 -4 3 -1 2 -4 3输出 #14说明/提示样例 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]为结尾最大值代码:#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN2e510;intn;LL f[N];//前缀和数组intmain(){cinn;for(inti1;in;i){LL x;cinx;f[i]f[i-1]x;}LL ret-1e20;LL prevmin0;for(inti1;in;i){retmax(ret,f[i]-prevmin);prevminmin(prevmin,f[i]);}coutretendl;return0;}注意题目中的数据范围prev是前驱的意思