前言
“前缀”相信大家对这个词都十分了解，“前缀和”更是大家所熟练的算法。而经过本人寒假刷题发现，前缀的东西也可以多种多样。
在本文中，calci=lr f(ai)\text{calc}_{i=l}^r \space f(a_i)calci=lr f(ai ) 表示 al calc al+1 calc ... calc ara_l \space \text{calc} \space a_{l+1}\space \text{calc} \space... \space \text{calc}\space a_ral calc al+1 calc ... calc ar ，其中 calc\text{calc}calc 是一种运算方法。
正文
前缀和
相信“前缀和”是大家接触“前缀”的起点，前缀和的定义为：有长度为 nnn 的数组 aia_iai ，那么前缀和数组 si=∑i=1nais_i = \sum_{i=1}^{n}a_isi =∑i=1n ai ，也可以写作 si={a1if i=1si−1+aiif i>1s_i = \left\{ \begin{array}{ll} a_1 & \text{if } i = 1 \\ s_{i-1} + a_i & \text{if } i > 1 \end{array}\right.si ={a1 si−1 +ai if i=1if i>1 。接下来，我们讲解两道题。
A336. 前缀和
这题是经典的模板题，按照上面的定义，因为 al+al+1+...+ar−1+ar=(a1+a2+...+ar−1+ar)−(a1+a2+...+al−1)a_l+a_{l+1} + ... + a_{r-1} + a_r = (a_1 + a_2 + ... + a_{r-1} + a_r) - (a_1 + a_2 + ... + a_{l-1})al +al+1 +...+ar−1 +ar =(a1 +a2 +...+ar−1 +ar )−(a1 +a2 +...+al−1 )，所以 ∑i=lrai=sr−sl−1\sum_{i=l}^r a_i=s_r-s_{l-1}∑i=lr ai
=sr −sl−1 ，输出 sr−sl−1s_r - s_{l-1}sr −sl−1 即可。
A83454. 定长区间总和
本题还有考虑每个数的贡献次数并求和解法，在这里只讨论前缀和解法。
题目求长度为 kkk 的连续区间的区间和之和。显然，对于一个 i (1≤i≤n−k+1)i\space(1 \le i \le n-k+1)i (1≤i≤n−k+1)，长度为 kkk 的区间是 [i,i+k−1][i, i+k-1][i,i+k−1]，其前缀和为 si+k−1−si−1s_{i+k-1} - s_{i-1}si+k−1 −si−1 ，输出 ∑i=1n−k***i+k−1−si−1\sum_{i=1}^{n-k+1} s_{i+k-1} - s_{i-1}∑i=1n−k****i+k−1 −si−1 即可。
前缀积
在阅读此章节前，你需要了解逆元。
【待补充】
前缀 GCD\TEXT{GCD}GCD
前缀 gcd\text{gcd}gcd 的定义为 gi=gcd i=1naig_i = \text{gcd}\space_{i=1}^{n}a_igi =gcd i=1n ai ，也可以写作 gi={a1if i=1gcd(si−1,ai)if i>1g_i = \left\{ \begin{array}{ll} a_1 & \text{if } i = 1 \\ \text{gcd}(s_{i-1}, a_i) & \text{if } i > 1 \end{array}\right.gi ={a1 gcd(si−1 ,ai ) if i=1if i>1 。
【待补充】
