C++知识点总结(9)：前缀和

一、前缀和

1. 意义

数列	15	20	30	50	65
下标	1	2	3	4	5
前缀和	15	35	65	115	180

2. 表示

前缀和：用数组表示，因为每一项的前缀和都能算出来。

3. 公式

值	前缀和数组
$a[1]$	$s[1]$
$s[1]+a[2]$	$s[2]$
$s[2]+a[3]$	$s[3]$
$...$	$...$
$s[i?1]+a[i]$	$s[i]$

4. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int a[100005] = {}; // 数组 
	int s[100005] = {}; // 前缀和数组 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式，存入数组 
	}
	
	int m; // m个求前缀和的数据
	int r;
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> r; // 输入前r项 
		cout << s[r] << endl;
	}
	return 0;
}

简化前思想时间复杂度 $O(n^2)$ ，简化后时间复杂度 $O(n)$ 。

二、区间和

1. 小节一下

知识点	公式
前缀和	$$sum=s[r?1]+a[i]$$
区间和	$$sum=s[r]?s[l?1]$$

2. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int a[100005] = {}; // 数组 
	int s[100005] = {}; // 前缀和数组 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式，存入数组 
	}
	
	int m; // m个求前缀和的数据
	int l, r; // l~r区间范围 
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l >> r; // 输入区间l和r 
		cout << s[r] - s[l-1] << endl; // 区间和公式，直接输出 
	}
	return 0;
}

三、喧闹的会议

1. 审题

一共有 $N$ 个席位，并视作一条直线，并且每个位置上的人都会和剩下的 $N?1$ 个位置上的所有人对线，第 $A$ 个位置的人和第 $B$ 个位置的人之间需要 $|A?B|$ 的音量才可以沟通。求总音量。

2. 思路

下表省略了 $abs$ 。

1	2	3	4	5
1-1	1-2	1-3	1-4	1-5
2-1	2-2	2-3	2-4	2-5
3-1	3-2	3-3	3-4	3-5
4-1	4-2	4-3	4-4	4-5
5-1	5-2	5-3	5-4	5-5

注意：

$|x?y|=|y?x|$ ，所以只用求下半部分。
而且，绝对值也可以去除了！

3. 优化

步骤	公式
举例	$$(5?1)+(5?2)+(5?3)+(5?4)+(5?5)$$
相当于	$$s[5]=5\times 5?s[5]$$
行和公式	$$rowsum=i\times a[i]?s[i]$$

4. 程序

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	long long a[100005] = {}; // 数组 
	long long s[100005] = {}; // 前缀和数组 
	long long sum = 0; // 会议总音量 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和公式，存入数组 
		
		// 计算每人音量和
		sum += (i * a[i] - s[i]);
	}
	cout << sum * 2;
	return 0;
}

四、被 $m$ 整除的最长区间

1. 同余定理

序号	等式
1	$$x÷a{=}_{.}..b$$
2	$$y÷a{=}_{.}..b$$
3	$$(x?y)÷a{=}_{.}..0$$

2. 审题

【题目描述】

给定一个正整数序列 $A$ ，其中包含 $N$ 个正整数，现请你找到在序列 $A$ 中存在的某一区间，使得该区间的区间和能够被 $M$ 整除，求出满足能够被 $M$ 整除的最长区间长度。若不存在则输出 $0$ 。

【输入描述】

共两行，第一行包含 $2$ 个正整数 $N$ 和 $M$ ，代表有 $N$ 个正整数以及除数M。

【输出描述】

一行，满足条件的最长区间长度。

【输入样例】

10 5
3 4 6 6 2 14 10 15 16 7

【输出样例】

9

【提示】

$1<=N<=50000,1<=M<=100$

3. 思路

前缀和属于区间和，是一个特殊的区间和，范围也就是 $1$ 至 $n$ 。

数组	3	4	6	6	2	14	10	15	16	7
下标	1	2	3	4	5	6	7	8	9	10
前缀和	3	7	13	19	21	35	45	60	76	83
余数	3	2	3	4	1	0	0	0	1	3
下标	1	2	3	4	5	6	7	8	9	10

我们可以增加一个 $pr[]$ 数组，表示每个余数第一次出现的位置。

pr[1] = 5;

如上，表示余数 $1$ 第一次出现的位置在下标 $5$ 的位置。
那么，得出了公式：

pr[r[i]] = i; // 桶的思想

晕了的童鞋，请看下面程序的注释。

4. 顺着代码捋

#include <iostream>
using namespace std;

int main()
{
	int n; // 项数 
	int m; // 除数 
	int a[50005] = {}; // 数组 
	int s[50005] = {}; // 前缀和数组 
	int r[50005] = {}; // 余数数组 
	int pr[50005] = {}; // 每个余数第一次出现的位置 
	int ans = 0; 
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i]; // 求前缀和 
		r[i] = s[i] % m; // 得到余数 
		
		if (r[i] == 0)
		{
			ans = max(ans, i); // 更行结果 
		}
		else
		{
			if (pr[r[i]] == 0) // 说明位置仍然为空 
			{
				pr[r[i]] = i; // 存储下标 
			}
			else
			{
				ans = max(ans, i - pr[r[i]]); 
			}
		}
	}
	
	cout << ans;
	return 0;
}