学习目标前缀和技巧差分技巧二维前缀和、二维差分区间类问题区间类问题在编程竞赛和算法设计中非常常见,它们通常涉及对数组或序列中的某个区间进行操作或查询。以下是一些常见的区间类问题类型:区间求和、区间更新、区间最值、区间统计、区间覆盖…选择合适的算法和数据结构是高效解决区间类问题的关键。比如用ST表求区间最值、用前缀和数组求区间和、用差分数组进行区间更新…前缀和什么是前缀和● 前缀和的定义数组a[1]~a[n],前缀和:s[i]a[1]a[2] …… a[i]s[1] a[1]s[2] a[1] a[2]s[3] a[1] a[2] a[3]● 递推关系我们已知前缀和的公式:s[i]a[1]a[2] … a[i-1]a[i]可以推出它的前一项:s[i - 1] a[1] a[2] … a[i - 1]所以递推公式是:s[i] s[i - 1] a[i]利用递推公式能在O(n)时间内求得所有前缀和前缀和的作用求区间和:给定n个整数,然后进行m次询问,每次询问求一个区间内值的和。对于给定的查询区间[i,j],区间和a[i]a[i1] …. a[j-1]a[j]。(1)暴力枚举法区间和a[i]a[i1] …… a[j-1]a[j]· 1次查询复杂度为O(n)· m次查询复杂度为O(nm)(2)前缀和法区间和s[j]-s[i-1]· 1次查询复杂度为O(1)· m次查询复杂度为O(m)注意,这里假设前缀和数组s[]已经存在。求区间和分两步:构建前缀和数组利用递推公式:s[i]s[i-1]a[i]快速查询[ij]区间和[ijj]区间和s[j]-s[i-1]时间复杂度为O(n)单次时间复杂度为O(1)· 大量查询更合算:总时间复杂度从暴力法的O(mn),变成O(n)O(m)。· 需要额外存储一个与原数组等长的前缀和数组,算法的空间复杂度通常为O(n)。●前缀和的典型应用是加速区间和计算和其他相关操作●前缀和的题目一般也能用暴力法求解●当题目有完成时间要求,并且需要做大量区间计算时,可以用前缀和优化●前缀和原理简单,方便在很多场景下应用,与其他考点结合,几乎必考二维前缀和二维数组----二维前缀和数组–快速计算二维区间和● 二维前缀和:s[i][j]表示所有a[i’][j’]的和(1≤i’≤i,1≤j’≤j)可以理解为“矩形的面积”那样,把一整块区域的值都加起来。例如,s[3][3] …左边图所示面积可以由两个行数或列数少一的矩形面积相加后,删去重合部分再加上右下角的值来构成(如右图所示)。二维区间和平衡序列小杨有一个包含n(1 n 10000)个正整数的序列a,他认为一个序列是平衡的当且仅当存在一个正整数i(1 in)使得序列第1到第i个数字的总和等于第i1到第n个数字的总和;小杨想请你判断序列a是否是平衡。【输入格式】第一行是一个正整数t(1 t 100),表示测试用例组数。接下来是t组测试用例。对每组测试用例,一共两行。第一行包含一个正整数n,表示序列长度。第二行包含n个正整数(1 ai 10000),代表序列a。【输出格式】对每组测试用例输出一行一个字符串。如果a是平衡的,输出Yes,否则输出No。【输入样例】331 2 342 3 1 451 2 3 4 5【输出样例】YesYesNo【样例说明】对于第一组测试用例,令i2,则有123,因此序列是平衡的;对于第二组测试用例,令i2,则有2314,因此序列是平衡的;对于第三组测试用例,不存在满足要求的i。(1)模拟法i的取值范围在1到n之间,所以最直观的想法就是对1到n进行枚举,测试所有的值,看看是否有i满足题目中的条件。for(1~t)组for(i1~n){① 循环得到a1到ai的和-s1(for1~i)②循环得到a(i1)到an的和-s2(fori1~n)③ 比较if(s1s2)...}最多需要3层循环,时间复杂度O(tn2)。当t、n取最大值时,tn21001000010000。执行次数远远大于1亿次,执行效率极低,容易超时。(2)前缀和法使用前缀和的技巧,一次创建前缀和数组,方便多次查询。①利用递推公式s[i]s[i-1]a[i],完成前缀和数组的赋值:for(inti1;in;i){//从下标1开始放。s[0]0cina[i];s[i]s[i-1]a[i];}② 第1到第个数字的总和s[i]等于第i1到第n个数字的总和?s[n] - s[i]if( s[i] s[n] - s[i])或者if( s[i]*2 s[n])相比模拟法,不用循环得到a1到ai的和,减少一层循环。基于前缀和法的流程(伪代码):for(1~t){//t组① 输入这组n个数,并计算前缀和s[]② 查找是否存在符合条件的ifor(i1~n){if(s[i]s[n]-s[i])找到了,设标记f1}③ 根据f标记输出Yes’或No}时间复杂度O(tn)#includeiostreamusingnamespacestd;intt,n,a[10010];//全局变量会自动初始化为0ints[10010];//前缀和数组。intmain(){cint;for(intil;it;i){cinn;for(intj1;jn;j){cina[j];s[j]s[j-1]a[j];}boolf0;//是否找到的符号,初始0,找到设为1for(intj1;jn;j){if(s[j]*2s[n]){f1;break;//找到一个就停止继续寻找}}if(f)coutYesendl;elsecoutNoendl;}return0;}· 如果a[]、s[]数组定义为局部变量,不要忘了初始化为0。· 标记f每次查找前必须初始为0。· 找到合适的i,可以加break优化。即马上停止继续查找。· 原始数组a[]在后续并不会用到,也可以省略,节约内存使用。两两相乘求和给定n个整数a1,a2,…,an,求他们两两相乘再相加的和,即:S a1a2 a1a3 … a1an a2a3 … an-2an-1 an-2an an-1*an【输入】第一行包含一个整数n,第二行包含n个整数a1,a2,…,an。【输出】输出一个整数S,表示所求的和。使用合适的数据类型进行运算。【数据范围】对于30%的数据,1≤n≤1000,1≤a;≤100。对于所有评测用例,1≤n≤200000,1≤a;≤1000。【输入样例】41369【输出样例】117(时间限制】1s竞赛题中的时间限制· 时间限制是编程竞赛中一个重要的约束条件,它不仅考验参赛者的算法设计和优化能力,还要求参赛者在有限的时间内找到最佳的解决方案。· 编程竞赛题的时间限制通常在题目中给出,C编程竞赛常见的时间限制是1秒。· 例如,如果一道题目的时间限制为1秒,而某个算法的时间复杂度为O(n^2),那么当输入规模n较大时,该算法将无法在规定时间内完成,导致超时,测试不能通过。· 因此,参赛者需要选择或优化算法,确保其时间复杂度尽可能低,以满足时间限制的要求。(1)模拟法直接按题目给的公式算,用两个for循环实现:// 按题目的公式求和for(inti1;in-1;i)for(intji1;jn;j)sa[i]*a[j];有2层for循环,循环次数是:n-1n-2.1~n2/2。时间复杂度O(n²)。本题有最大运行时间1s的运行限制。若n200000,循环次数2000002/22×10¹º。很可能会因为超时,不能通过测试。(2)前缀和法基于前缀和法的流程(伪代码):1.输入这组n个数,并计算前缀和sum[]2.用上面的基于前缀和的公式计算s(初始为0)for(i1~n){sa[i]*(sum[n]-sum[i]);}3.输出s 时间复杂度O(n)完整代码案例#includeiostreamusingnamespacestd;inta[200010];longlongsum[200010];//前缀和数组intmain(){intn;scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);sum[i]sum[i-1]a[i];//预计算前缀和}longlongs0;//注意局部变量定义时要初始化为0for(inti1;in;i)sa[i]*(sum[n]-sum[i]);printf(%lld\n,s);return0;}· 如果a[]、s[]数组定义为局部变量,不要忘了整体初始化为0· 变量s要开long long 防止溢出差分差分的概念差分的定义:即差分数组D[]是原数组a[]的相邻元素的差。D[k] a[k]-a[k-1]根据D[]的定义,可以反过来推出:a[k] D[1] D[2] … D[k] a[k-1]D[k]即a[]是D[]的前缀和,所以“差分是前缀和的逆运算”。差分的作用区间修改:假设有m次操作,每次将a数组中下标为[L,R]之间的数都加上x。(数组长度n)(1)暴力法L~R的区间,逐个X· 1次修改O(n)· m次修改O(mn)(2)差分法基于差分数组D[],只改动两个点的值:把D[L]加上x:D[L]x把D[R1]减去x: D[R1] - x· 1次修改O(1)· m次修改O(m)差分数组的作用:● 应用于区间的整体修改和询问问题,特别是多次修改后的询问● 当所有的修改操作结束后,再利用差分数组,计算出新的a[]二维差分差分求二维前缀和小A倒水在一个桌子上摆放了n个杯子,每个杯子中有一定量的水。小A同学负责向杯子中倒水,他总共倒了k次,每次会向从第L个杯子到第R个杯子中添加P毫升的水(注意:水只可能增加,不可能减少)。请问小A同学倒了k次水之后,n个杯子每个杯子有多少毫升的水。【输入】第一行包含两个整数n和k。第二行包含n个整数,表示一开始每个杯子中水的毫升数。接下来k行,每行包含三个整数L,R,P,表示一次操作。【输出】共一行,包含n个整数,表示最终n个杯子每个杯子有多少毫升的水。【数据范围】1≤n,k≤100000.1≤L≤R≤n.0≤P≤1000.杯子中水的初始量在[0,1000]的范围内。本题数据上保证所有的杯子在加水之后,水量值仍然在int范围内。【输入样例】8 31 2 10 8 15 1 17 8 121 8 42 3 12【输出样例】5 18 26 12 5 9 17 17对数列进行k次任取区间的修改,问最终数列的值。差分法!步骤:①输入原数数据到a[],并计算差分D[]D[i] a[i] - a[i-1]②k次更新差分数组DD[L] x, D[R1] - x③求D[]的前缀和,就是a数组做了k次操作的后结果a[i] a[i-1]D[i]#includeiostreamusingnamespacestd;inta[100010],D[100010];//a代表读入的原数组,D代表是差分数组intn,k,L,R,p;intmain(){cinnk;// 输入原数数据,从下标1开始放。a[0]0for(inti1;in;i){cina[i];//求差分数组D[i]a[i]-a[i-1];}// k次倒水,更新差分数组for(inti1;ik;i){cinLRp;D[L]p;D[R1]-p;}//求D数组的前缀和,就是a数组做了k次操作的结果for(inti1;in;i){a[i]a[i-1]D[i];// 即累加 D[0]~D[i]couta[i] ;}return0;}时间复杂度O(n)· 有效数据从a[1]、D[1]开始放· D[1]a[1]-a[0],所以要确保a[0]0本次课程的知识点二维前缀和数组、二维差分数组前缀和的概念用前缀数组和求区间和差分的概念用差分数组进行区间修改1、已知字符‘A’的ASCII编码的十六进制表示为0x41,则字符’L’的ASCII编码的十六进制表示为?CA、0x4AB、0x4BC、0x4CD、0x52【提示】‘A’的十进制ASCII编码4*16165。可算出’L’的十进制ASCII编码64’[~A’的间隔651176,76转回十六进制0x4C。连续数的和给出两个整数n和k,(2≤n≤70000,1≤k≤n),求出1、2、3、…、n中连续k个数的和,并计算出和为平方数的个数。【输入】n、k两个整数。【输出】一个整数,即1、2、3、…、n中连续k个数的和为平方数的个数。【输入样例1】10 3【输出样例1】1【输入样例2】100 3【输出样例2】5【样例1说明】n10, k3.在1,2,…,10中,连续3个数的和有:123623493451245615567186782178924891027其中和为平方数的仅有9,因为93×3。(模拟法代码示例】#includeiostream#includecmathusingnamespacestd;// 一个整数n是否平方数boolissquare(longlongn){longlongmsqrt(n);//求n的平方根,类型转换时向下取整returnm*mn;}intmain(){intn,k;scanf(%d %d,n,k);intcnt0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间[i,ik-1]区间和 sum[ik-1]-sum[i-for(inti1;in-k1;i){// 累加 k个连续数:si(i1) ... (ik-1) k*ilonglongsi*kk*(k-1)/2;if(is_square(s))cnt;}printf(%d\n,cnt);return0;}【前缀和法代码示例】#includeiostream#includecmathusingnamespacestd;longlongsum[70010];//前缀和数组// 一个整数n是否平方数boolis_square(longlongn){longlongmsqrt(n);//求n的平方根,类型转换时向下取整returnm*mn;}intmain(){intn,k;scanf(%d %d,n,k);for(inti1;in;i)sum[i]sum[i-1]i;//预计算前缀和intcnt0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间[i,ik-1]区间和sum[ik-1]-sum[i-1]for(inti1;in-k1;i){if(is_square(sum[ik-1]-sum[i-1]))cnt;}printf(%d\n,cnt);return0;}可以用模拟法,也可以用前缀和法。模拟法可以借助等差数列和的计算公式进行优化:12 … kk*(k1)/2。优化后模拟法和前缀和法的时间复杂度相同O(n)。