学习目标

  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(for 1~i)
	②循环得到a(i+1)到an的和 ->s2(for i+1~n)
	③ 比较 if(s1 == s2) ...

}

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

(2)前缀和法

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

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

for (int i=1;i <= n; i++) {//从下标1开始放。s[0]=0
	cin >> 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[]
	② 查找是否存在符合条件的i
	for(i = 1~n) {
		if (s[i] == s[n] - s[i])
			找到了,设标记f=1
	}
	③ 根据f标记输出"Yes’或"No"
}

时间复杂度O(tn)

#include <iostream>
using namespace std;
int t,n,a[10010];//全局变量会自动初始化为0
int s[10010];//前缀和数组。

int main() {
	cin >> t;
	for (int i=l;i <= t; i++) {
	cin >> n;
	
	for (int j=1;j <= n;j++) {
		cin >> a[j] ;
		s[j] = s[j-1]+a[j] ;
	}
	bool f=0;//是否找到的符号,初始0,找到设为1
	for (int j=1;j <= n; j++) {
		if (s[j]*2 == s[n]) {
		f =1;
		break;//找到一个就停止继续寻找
	
		}
	}
	
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	}
	return 0;
}

· 如果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(int i=1;i <= n-1; i++)
	for(int j=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>
using namespace std;
int a[200010] ;
long long sum [200010] ;	//前缀和数组

int main () {
	int n;
	scanf ("%d", &n) ;
	for(int i=1; i <= n; i++){
		scanf ("%d", &a[i]) ;
		sum [i] = sum[i-1] +a[i] ;//预计算前缀和
	}
	long long s=0; //注意局部变量定义时要初始化为0
	for(int i=1; i <= n; i++)
		s += a[i] * (sum [n] -sum [i] ) ;
	printf("%lld\n", s) ;
	return 0;
}

· 如果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>
using namespace std;

int a[100010],D[100010];//a代表读入的原数组,D代表是差分数组
int n,k,L,R,p;

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

时间复杂度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>
using namespace std;

// 一个整数n是否平方数
bool is square (long long n) {
	long long m= sqrt(n);//求n的平方根,类型转换时向下取整
	return m*m == n;
}
int main(){
	int n,k;
	scanf ("%d %d", &n, &k) ;
	
	int cnt=0;//注意局部变量定义时要初始化为0
	// 逐个查看区间和是否是平方数
	// 连续k个数的区间[i,i+k-1]区间和= sum[i+k-1]-sum[i-
	for(int i=1; i <= n-k+1; i++) {
		// 累加 k个连续数:s=i+(i+1)+ ... +(i+k-1) =k*i
		long long s = i*k + k*(k-1) /2;
		if(is_square (s))
			cnt++;
	}
	printf("%d\n", cnt) ;
	return 0;
}

【前缀和法代码示例】

#include <iostream>
#include <cmath>
using namespace std;
long long sum [70010] ;//前缀和数组

// 一个整数n是否平方数
bool is_square (long long n) {
	long long m=sqrt(n);//求n的平方根,类型转换时向下取整
	return m*m == n;
}

int main(){
	int n,k;
	scanf ("%d %d", &n, &k) ;
	for(int i=1; i <= n; i++)
		sum[i] = sum[i-1] + i;//预计算前缀和
	
	int cnt=0;//注意局部变量定义时要初始化为0
	// 逐个查看区间和是否是平方数
	// 连续k个数的区间[i,i+k-1]区间和=sum[i+k-1]-sum[i-1]
	for(int i=1; i <= n-k+1; i++) {
		if(is_square (sum[i+k-1] - sum[i-1] ))
			cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

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

# c++ # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！人工智能的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区