C++（前缀和与差分）

学习目标

1. 前缀和技巧
2. 差分技巧
3. 二维前缀和、二维差分

区间类问题

区间类问题在编程竞赛和算法设计中非常常见,它们通常涉及对数组或序列中的某个区间进行操作或查询。以下是一些常见的区间类问题类型:区间求和、区间更新、区间最值、区间统计、区间覆盖…选择合适的算法和数据结构是高效解决区间类问题的关键。比如用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[i+1]+ …. +a[j-1]+a[j]。

(1)暴力枚举法
区间和=a[i]+a[i+1]+ …… +a[j-1]+a[j]
· 1次查询复杂度为O(n)
· m次查询复杂度为O(nm)

(2)前缀和法
区间和=s[j]-s[i-1]
· 1次查询复杂度为O(1)
· m次查询复杂度为O(m)
注意,这里假设前缀和数组s[]已经存在。

求区间和分两步:

1. 构建前缀和数组
   利用递推公式:s[i]=s[i-1]+a[i]
2. 快速查询[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 <= i<n)使得序列第1到第i个数字的总和等于第i+1到第n个数字的总和;小杨想请你判断序列a是否是平衡。
【输入格式】
第一行是一个正整数t(1 <= t <= 100),表示测试用例组数。
接下来是t组测试用例。
对每组测试用例,一共两行。第一行包含一个正整数n,表示序列长度。第二行包含n个
正整数(1 <= ai <= 10000),代表序列a。
【输出格式】对每组测试用例输出一行一个字符串。如果a是平衡的,输出Yes,否则输
出No。
【输入样例】
3
3
1 2 3
4
2 3 1 4
5
1 2 3 4 5
【输出样例】
Yes

Yes

No

【样例说明】
对于第一组测试用例,令i=2,则有1+2=3,因此序列是平衡的;
对于第二组测试用例,令i=2,则有2+3=1+4,因此序列是平衡的;
对于第三组测试用例,不存在满足要求的i。

(1)模拟法

i的取值范围在1到n之间,所以最直观的想法就是对1到n进行枚举,测试所有的值,看看是否有i满足题目中的条件。

for(1~t)组for(i=1~n){① 循环得到a1到ai的和->s1(for1~i)②循环得到a(i+1)到an的和->s2(fori+1~n)③ 比较if(s1==s2)...}

最多需要3层循环,时间复杂度O(tn2)。当t、n取最大值时,tn2=1001000010000。执行次数远远大于1亿次,执行效率极低,容易超时。

(2)前缀和法

使用前缀和的技巧,一次创建前缀和数组,方便多次查询。

①利用递推公式s[i]=s[i-1]+a[i],完成前缀和数组的赋值:

for(inti=1;i<=n;i++){//从下标1开始放。s[0]=0cin>>a[i];s[i]=s[i-1]+a[i];}

② 第1到第个数字的总和（s[i]）等于第i+1到第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(i=1~n){if(s[i]==s[n]-s[i])找到了,设标记f=1}③ 根据f标记输出"Yes’或"No"}

时间复杂度O(tn)

#include<iostream>usingnamespacestd;intt,n,a[10010];//全局变量会自动初始化为0ints[10010];//前缀和数组。intmain(){cin>>t;for(inti=l;i<=t;i++){cin>>n;for(intj=1;j<=n;j++){cin>>a[j];s[j]=s[j-1]+a[j];}boolf=0;//是否找到的符号,初始0,找到设为1for(intj=1;j<=n;j++){if(s[j]*2==s[n]){f=1;break;//找到一个就停止继续寻找}}if(f)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}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。
【输入样例】4

1369

【输出样例】117
(时间限制】1s

竞赛题中的时间限制

· 时间限制是编程竞赛中一个重要的约束条件,它不仅考验参赛者的算法设计和优化能
力,还要求参赛者在有限的时间内找到最佳的解决方案。

· 编程竞赛题的时间限制通常在题目中给出,C++编程竞赛常见的时间限制是1秒。
· 例如,如果一道题目的时间限制为1秒,而某个算法的时间复杂度为O(n^2),那么当输入规
模n较大时,该算法将无法在规定时间内完成,导致超时,测试不能通过。
· 因此,参赛者需要选择或优化算法,确保其时间复杂度尽可能低,以满足时间限制的要求。

(1)模拟法

直接按题目给的公式算,用两个for循环实现:

// 按题目的公式求和for(inti=1;i<=n-1;i++)for(intj=i+1;j<=n;j++)s+=a[i]*a[j];

有2层for循环,循环次数是:n-1+n-2+.+1~n2/2。时间复杂度O(n²)。
本题有最大运行时间1s的运行限制。
若n=200000,循环次数2000002/2=2×10¹º。很可能会因为超时,不能通过测试。

(2)前缀和法

基于前缀和法的流程(伪代码):

1.输入这组n个数,并计算前缀和sum[]2.用上面的基于前缀和的公式计算s(初始为0)for(i=1~n){s+=a[i]*(sum[n]-sum[i]);}3.输出s 时间复杂度O(n)

完整代码案例

#include<iostream>usingnamespacestd;inta[200010];longlongsum[200010];//前缀和数组intmain(){intn;scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];//预计算前缀和}longlongs=0;//注意局部变量定义时要初始化为0for(inti=1;i<=n;i++)s+=a[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[],只改动两个点的值:

1. 把D[L]加上x:D[L]+=x
2. 把D[R+1]减去x: D[R+1] -= 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 3

1 2 10 8 15 1 1

7 8 12

1 8 4

2 3 12
【输出样例】
5 18 26 12 5 9 17 17
对数列进行k次任取区间的修改,问最终数列的值。差分法!

步骤:

①输入原数数据到a[],并计算差分D[]
D[i] = a[i] - a[i-1]
②k次更新差分数组D
D[L] += x, D[R+1] -= x
③求D[]的前缀和,就是a数组做了k次操作的后结果
a[i] = a[i-1]+D[i]

#include<iostream>usingnamespacestd;inta[100010],D[100010];//a代表读入的原数组,D代表是差分数组intn,k,L,R,p;intmain(){cin>>n>>k;// 输入原数数据,从下标1开始放。a[0]=0for(inti=1;i<=n;i++){cin>>a[i];//求差分数组D[i]=a[i]-a[i-1];}// k次倒水,更新差分数组for(inti=1;i<=k;i++){cin>>L>>R>>p;D[L]+=p;D[R+1]-=p;}//求D数组的前缀和,就是a数组做了k次操作的结果for(inti=1;i<=n;i++){a[i]=a[i-1]+D[i];// 即累加 D[0]~D[i]cout<<a[i]<<" ";}return0;}

时间复杂度O(n)

· 有效数据从a[1]、D[1]开始放
· D[1]=a[1]-a[0],所以要确保a[0]=0

本次课程的知识点

1. 二维前缀和数组、二维差分数组

2. 前缀和的概念

3. 用前缀数组和求区间和

4. 差分的概念

5. 用差分数组进行区间修改

1、已知字符‘A’的ASCII编码的十六进制表示为0x41,则字符’L’的
ASCII编码的十六进制表示为?（C）

A、0x4A

B、0x4B

C、0x4C

D、0x52

【提示】‘A’的十进制ASCII编码=4*16+1=65。可算出’L’的十进制ASCII编码=64+’[~'A’的
间隔=65+11=76,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说明】
n=10, k=3.
在1,2,…,10中,连续3个数的和有:
1+2+3=6
2+3+4=9
3+4+5=12
4+5+6=15
5+6+7=18
6+7+8=21
7+8+9=24
8+9+10=27
其中和为平方数的仅有9,因为9=3×3。

(模拟法代码示例】

#include<iostream>#include<cmath>usingnamespacestd;// 一个整数n是否平方数boolissquare(longlongn){longlongm=sqrt(n);//求n的平方根,类型转换时向下取整returnm*m==n;}intmain(){intn,k;scanf("%d %d",&n,&k);intcnt=0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间[i,i+k-1]区间和= sum[i+k-1]-sum[i-for(inti=1;i<=n-k+1;i++){// 累加 k个连续数:s=i+(i+1)+ ... +(i+k-1) =k*ilonglongs=i*k+k*(k-1)/2;if(is_square(s))cnt++;}printf("%d\n",cnt);return0;}

【前缀和法代码示例】

#include<iostream>#include<cmath>usingnamespacestd;longlongsum[70010];//前缀和数组// 一个整数n是否平方数boolis_square(longlongn){longlongm=sqrt(n);//求n的平方根,类型转换时向下取整returnm*m==n;}intmain(){intn,k;scanf("%d %d",&n,&k);for(inti=1;i<=n;i++)sum[i]=sum[i-1]+i;//预计算前缀和intcnt=0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间[i,i+k-1]区间和=sum[i+k-1]-sum[i-1]for(inti=1;i<=n-k+1;i++){if(is_square(sum[i+k-1]-sum[i-1]))cnt++;}printf("%d\n",cnt);return0;}

可以用模拟法,也可以用前缀和法。模拟法可以借助等差数列和的计算公式进行优化:
1+2+ … +k=k*(k+1)/2。优化后模拟法和前缀和法的时间复杂度相同O(n)。