难度普及− 知识点一维前缀和 所属专栏【洛谷题解】前置知识《一维前缀和详解》目录一、题目描述二、题目分析1. 暴力做法2. 为什么想到前缀和3. 用样例模拟一遍三、代码实现1. 算法思路2. C代码实现四、细节补充1. 这道题需要开 long long 吗2. 复杂度分析五、总结一、题目描述题目链接P8218 【深进1.例1】求区间和【题目描述】给定由n nn个正整数组成的序列a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1,a2,⋯,an和m mm个区间[ l i , r i ] [l_i, r_i][li,ri]分别求这m mm个区间的区间和。【输入格式】第一行包含一个正整数n nn表示序列的长度。第二行包含n nn个正整数a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1,a2,⋯,an。第三行包含一个正整数m mm表示区间的数量。接下来m mm行每行包含两个正整数l i , r i l_i, r_ili,ri满足1 ≤ l i ≤ r i ≤ n 1 \le l_i \le r_i \le n1≤li≤ri≤n。【输出格式】共m mm行其中第i ii行包含一个正整数表示第i ii组答案的询问。【输入样例】44 3 2 121 42 3【输出样例】105【说明/提示】第1 11到第4 44个数加起来和为10 1010第2 22个数到第3 33个数加起来和为5 55。对于50 % 50\%50%的数据n , m ≤ 1000 n, m \le 1000n,m≤1000对于100 % 100\%100%的数据1 ≤ n , m ≤ 10 5 1 \le n, m \le 10^51≤n,m≤1051 ≤ a i ≤ 10 4 1 \le a_i \le 10^41≤ai≤104。二、题目分析这道题的题意非常直接给一个数组多次询问某一段区间的和。看到这样的题目我们先不急着套算法而是从最朴素的做法开始想。1. 暴力做法最容易想到的做法是每次询问就用一个循环从a l a_lal加到a r a_rar。for(inti1;im;i){intl,r,sum0;scanf(%d%d,l,r);for(intjl;jr;j)suma[j];// 每次询问都重新累加printf(%d\n,sum);}这个做法思路完全正确但我们要结合数据范围来判断它能不能通过。对于50 % 50\%50%的数据n , m ≤ 1000 n, m \le 1000n,m≤1000最坏情况下要计算1000 × 1000 10 6 1000 \times 1000 10^61000×1000106次完全没有压力。对于100 % 100\%100%的数据n , m ≤ 10 5 n, m \le 10^5n,m≤105最坏情况下每次询问都是[ 1 , n ] [1, n][1,n]总共要计算10 5 × 10 5 10 10 10^5 \times 10^5 10^{10}105×1051010次远远超过计算机 1 秒约10 8 10^8108次的运算能力一定会超时。所以暴力做法大约只能拿到一半的分数。我们需要一种能快速回答每一次询问的方法。2. 为什么想到前缀和我们来观察一下这道题的特点数组在输入之后不会再被修改需要多次询问区间和。“静态数组 多次区间求和”这正是前缀和最典型的使用场景。在《一维前缀和详解》中我们已经推导过s i s i − 1 a i , a l a l 1 ⋯ a r s r − s l − 1 s_i s_{i-1} a_i, \qquad a_l a_{l1} \cdots a_r s_r - s_{l-1}sisi−1ai,alal1⋯arsr−sl−1先用O ( n ) O(n)O(n)的时间求出前缀和数组之后每次询问只需要做一次减法时间复杂度降到O ( 1 ) O(1)O(1)。3. 用样例模拟一遍在写代码之前我们先用样例手动模拟一遍确认思路没有问题。数组为4 , 3 , 2 , 1 4, 3, 2, 14,3,2,1先求出前缀和数组下标i ii01234a i a_iai-4321s i s_isi047910接下来回答两次询问询问[ 1 , 4 ] [1, 4][1,4]s 4 − s 0 10 − 0 10 s_4 - s_0 10 - 0 10s4−s010−010✅询问[ 2 , 3 ] [2, 3][2,3]s 3 − s 1 9 − 4 5 s_3 - s_1 9 - 4 5s3−s19−45✅两个结果都和样例输出一致说明思路是正确的接下来就可以动手写代码了。三、代码实现1. 算法思路根据上面的分析代码可以分为三个部分读入n nn和数组同时求出前缀和读入m mm依次读入每次询问的l ll和r rr用s r − s l − 1 s_r - s_{l-1}sr−sl−1计算并输出答案我们根据思路一步一步来实现①首先读入数组。和模板一样我们一边读入一边求前缀和数组下标从1 11开始scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}②这道题的输入格式需要注意m mm是在数组之后才读入的而不是和n nn一起在第一行。很多同学习惯性地写成scanf(%d%d, n, m)结果读入全部错位。所以这里要单独读入m mmscanf(%d,m);③最后处理每一次询问代入公式输出答案while(m--){intl,r;scanf(%d%d,l,r);printf(%lld\n,s[r]-s[l-1]);}2. C代码实现最后我们将代码整合一下完整代码如下#includebits/stdc.husingnamespacestd;constintN100010;intn,m,a[N];longlongs[N];// 前缀和数组intmain(){// ① 读入数组同时求前缀和scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}// ② 注意m 在数组之后读入scanf(%d,m);// ③ O(1) 回答每一次询问while(m--){intl,r;scanf(%d%d,l,r);printf(%lld\n,s[r]-s[l-1]);}return0;}四、细节补充1. 这道题需要开 long long 吗我们来算一下前缀和的最大值最多10 5 10^5105个数每个数最大10 4 10^4104所以前缀和最大为10 5 × 10 4 10 9 10^5 \times 10^4 10^9105×104109。而int的最大值约为2.1 × 10 9 2.1 \times 10^92.1×109所以这道题用int其实也不会溢出。但是并不是每道前缀和题目的数据都这么友好只要a i a_iai的范围稍微大一点int就会溢出。所以还是建议大家养成前缀和数组默认开long long的习惯这样就不用每次都去计算会不会溢出。2. 复杂度分析时间复杂度预处理O ( n ) O(n)O(n)每次询问O ( 1 ) O(1)O(1)总计O ( n m ) O(n m)O(nm)。空间复杂度O ( n ) O(n)O(n)。对于n , m ≤ 10 5 n, m \le 10^5n,m≤105的数据前缀和做法只需要约2 × 10 5 2 \times 10^52×105次运算轻松通过。五、总结这是一道非常标准的一维前缀和模板题做这道题时要掌握以下几点识别题型看到静态数组 多次区间求和要第一时间想到前缀和结合数据范围10 5 10^5105规模的多次询问暴力O ( n m ) O(nm)O(nm)会超时需要O ( 1 ) O(1)O(1)回答询问注意输入格式本题的m mm在数组之后读入记住公式区间和是s r − s l − 1 s_r - s_{l-1}sr−sl−1减去的是左端点前一个位置的前缀和。掌握了这道模板题之后可以继续挑战下一道练习题 P6568 [NOI Online #3 提高组] 水壶看看前缀和在定长区间问题中是怎么用的。相关文章《一维前缀和详解》下一篇题解P6568 水壶如果这篇题解对你有帮助欢迎点赞、收藏、关注每周持续更新 CSP-J 知识点和洛谷题解。