一维前缀和笔记

求和符号简介

在数学中求和符号为 $\sum$，叫做 sigma。

该符号主要是对某一连续的数字的和的一种简写表达方式。例如：

• $\sum_{i=1}^n i=1+2+\cdots+n$
• $\sum_{i=1}^n a_i=a_1+a_2+\cdots+a_n$
• $\sum_{i=1}^n \sum_{j=1}^n a_{i,j}=a_{1,1}+a_{1,2}+\cdots+a_{1,n}+a_{2,1}+a_{2,2}+\cdots+a_{2,n}+\cdots+a_{n,n}$

一维前缀和

定义：$sum_i$ 为 $\sum_{j=1}^i a_j$。即 $sum_i=a_1+a_2+\cdots+a_i$。

• $sum_1=a_1$
• $sum_2=a_1+a_2$
• $sum_n=a_1+a_2+\cdots+a_n$

观察到其满足一个递推关系，即

$$sum_{i}=sum_{i-1}+a_i$$

因此使用递推即可维护。

获取某一段区间范围 $i\sim j$ 内的数字之和，可以使用 $sum_j-sum_{i-1}$ 得到。

证明： 根据上述定义： $sum_{i-1}=a_1+a_2+\cdots+a_{i-1}$。

$sum_j=a_1+a_2+\cdots+a_{i-1}+a_i+\cdots+a_j$。

二者做差即可得到

$a_i+a_{i+1}+\cdots+a_j$。

常见应用

• 在题目中明确给出了一段区间范围 $i\sim j$ 且 $i\leq j$ 。那么我们通过 $sum_j - sum_{i - 1}$ 可以得到该段区间范围数字的和。
• 在题目中只能获取一个端点的信息，但同时也给定了区间的长度 $len$ 那么我们可以通过一个端点和区间长度计算出另一个端点。然后使用前缀和的公式。
• 注意前缀和不要仅仅局限于和字，例如也可以使用前缀和算法计算区间质数个数，区间奇数个数等。

其它形式的前缀和

• 乘积的前缀

定义 $sum_i=a_1\times a_2\times \cdots \times a_i$

则区间 $i\sim j$ 的数值乘积可以通过 $\frac{sum_j}{sum_{i-1}}$ 得到。

但是乘积的题目若牵扯取余，就需要利用一些其他知识来解决除法运算不能边计算边取余的问题。

• 异或的前缀

定义 $sum_i=a_1\oplus a_2\oplus \cdots \oplus a_i$

则区间 $i\sim j$ 的数值异或和可以通过 $sum_j\oplus sum_{i-1}$ 得到。

因为 $sum_j=a_1\oplus a_2\oplus \cdots \oplus a_j$

$sum_{i-1}=a_1\oplus a_2\oplus \cdots \oplus a_{i-1}$

异或的计算规则为 相同为 0，不同为 1，因此同样的数字异或两次后为 $0$

因此 $sum_j\oplus sum_{i-1}$ 以后，$a_1\sim a_{i-1}$ 会各自异或两次，全部消掉。

求区间里有多少个奇数。

将奇数看作 $1$，偶数看作 $0$，则一个区间内有多少个奇数，可以看作是求有多少个 $1$。

也可以看作是求该区间内的数字之和（此时数字不是 $1$ 就是 $0$）。

求区间和？这不就又转化到了前缀和上。即本题的前缀和维护如下：

$$sum_{i}=\begin{cases} sum_{i-1}+1,a_i\ is\ odd\\ sum_{i-1}+0,a_i\ is\ even \end{cases} $$

$even$ 是偶数，$odd$ 是奇数。

后缀

定义：$suf_i$ 为 $a_i+a_{i+1}+a_{i+2}+\cdots+a_n$。

后缀的区间和公式：

$$suf_i-suf_{j+1}$$

需要保证 $i\leq j$。

注意由于是后缀，所以后缀的求解是倒着遍历序列来完成的。即

$$suf_i=suf_{i+1}+a_i$$

常见应用

• 应用在序列分成两部分的情况，前半部分通过预处理一个前缀，后半部分通过预处理后缀，然后合并两部分的答案求解问题。

举例

在第五题中，我们暴力做法如下：

for (int i = 1; i <= n; i++)
{
	// 暴力 
	long long sum = 1;
	for (int j = 1; j <= i - 1; j++)
		sum = sum * a[j] % mod;
	for (int j = i + 1; j <= n; j++)
		sum = sum * a[j] % mod; 
	cout << sum << endl;
}

而内部的两个循环完全可以通过预处理前缀积和后缀积解决，使得 $O(1)$ 的复杂度求出去掉每个数字的和。