前缀和

📌 概述

---

🎯 核心概念

什么是前缀和？

即数列前 $i$ 项的和：

\[ pre_i \;=\; a_1 + a_2 + \cdots + a_i \]

它能做什么？

• 快速获取区间和、区间内质数/奇数/偶数个数等
• 可拓展至：前缀积、前缀异或等

---

🔍 一维前缀和

1️⃣ 定义

• 令

\[ pre_i = \sum_{j=1}^i a_j \quad\Longrightarrow\quad pre_i = a_1 + a_2 + \cdots + a_i \]

• 例如：

  • $pre_1 = a_1$
  • $pre_2 = a_1 + a_2$
  • $\cdots$
  • $pre_n = a_1 + a_2 + \cdots + a_n$

• 递推关系

\[ pre_i = pre_{i-1} + a_i \]

for (int i = 1; i <= n; i++) 
{
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
}

💡 注意数据范围是否需要 long long。

---

性质

• 区间和查询

求区间 $i \sim j$ 内的数字之和，可以使用

\[ pre_j - pre_{i-1} \]

证明：

\[ \begin{aligned} pre_j &= a_1 + a_2 + \cdots + a_{i-1} + a_i + \cdots + a_j,\\ pre_{i-1} &= a_1 + a_2 + \cdots + a_{i-1},\\ \Rightarrow\, pre_j - pre_{i-1} &= a_i + \cdots + a_j \end{aligned} \]

---

常见应用

• 给定区间的左右端点 $l, r$，可以通过

\[ pre_r - pre_{l-1} \]

查询区间 $[a_l,\ldots,a_r]$ 和。

---

• 已知左端点 $l$ 和区间长度 $len$，则右端点为 $r = l + len - 1$。然后用

\[ pre_r - pre_{l-1} \]

查询区间 $[a_l,\ldots,a_r]$ 和。

---

注意

前缀和不仅仅局限于 和。它主要是预处理的算法，通过一段前缀减去另一段前缀，得到某一段区间的信息。例如：

• 区间内质数个数
• 区间内奇数/偶数个数/含有 $3$ 的数字个数等
• 区间异或值等

---

其它形式的前缀和

前缀和不仅适用于求和，还可以拓展到其他运算，如乘积、异或等。

---

前缀乘积

定义：

\[ pre_i = a_1 \times a_2 \times \cdots \times a_i \]

区间乘积计算方式：

\[ \displaystyle a_i \times a_{i+1} \times \cdots \times a_j = \frac{pre_j}{pre_{i-1}} \]

• 容易爆 $\texttt{long long}$，要格外注意数据范围。通常伴随取余。
• 若题目要求对结果取模，涉及除法时需用 乘法逆元，未掌握前建议慎用。
• 初始化：$pre_0=1$。

---

前缀异或

定义：

\[ pre_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i \]

区间异或计算方式：

\[ a_i \oplus a_{i+1} \oplus \cdots \oplus a_j = pre_j \oplus pre_{i - 1} \]

证明：利用异或性质：$x \oplus x = 0$。

---

区间某性质的数字个数

以求区间内有多少个奇数为例。

• 将每个元素转化为：奇数记为 $1$，偶数记为 $0$
• 问题转化为：统计区间中值为 $1$ 的个数 —— 即该区间的和

本质：利用前缀和统计 $[l, r]$ 区间中有多少个奇数。

定义前缀和数组 $pre$，其中：

\[ pre_i = \begin{cases} pre_{i - 1} + 1, & \text{若 }\ a_i \text{ 为奇数} \\ pre_{i - 1}, & \text{若 }\ a_i \text{ 为偶数} \end{cases} \]

那么，区间 $[l, r]$ 中奇数的个数即为：

\[ pre_r - pre_{l - 1} \]

类比可以解决区间质数个数，区间内满足某某条件的数字个数等等。

---

后缀和

同样可以拓展出后缀积、后缀异或等。

定义：设 $suf_i$ 表示从第 $i$ 项到第 $n$ 项的和，即：

\[ suf_i = a_i + a_{i+1} + a_{i+2} + \cdots + a_n \]

suf 是单词 $\texttt{suffix}$（后缀）的简写。

类似前缀和，我们也可以通过后缀和来快速求解任意区间 $[i, j]$ 的和（$i \leq j$）：

\[ \text{区间和 } = suf_i - suf_{j+1} \]

---

具体实现

注意：后缀和的计算方式是从后往前递推：

\[ suf_i = suf_{i+1} + a_i \]

for (int i = n; i >= 1; i--)
{
    suf[i] = suf[i + 1] + a[i];
}

应用场景：适用于需频繁查询 尾部区间 的问题，如找出后缀最小值、最大和子数组的后缀版本等。

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

---

📚 二维前缀和

预处理：二维前缀和

• 定义二维前缀和数组

令 $\displaystyle pre[i][j]$ 表示矩阵 $a$ 中子矩阵 $[1..\,i]\times [1..\,j]$ 的元素之和，即

\[ pre[i][j] \;=\; \sum_{x=1}^{i} \sum_{y=1}^{j} a_{x,y}, \quad 1 \le i \le n,\;1 \le j \le m. \]

---

• 递推公式

\[ pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1] + a_{i,j} \]

即 蓝 + 黄 + 绿 + 橙 = (蓝 + 黄) + (蓝 + 绿) - 蓝 + 橙 最终求得了 $pre_{i, j}$

---

考虑一个具体的例子。

其中，$S$ 是矩阵 $A$ 的前缀和。根据定义，$S_{3,3}$ 是左图中虚线方框中的子矩阵的和。而且，$S_{3,2}$ 是蓝色子矩阵的和，$S_{2,3}$ 是红色子矩阵的和，它们重叠部分的和是 $S_{2,2}$。由此可见，如果直接相加 $S_{3,2}$ 和 $S_{2,3}$，会重复计算 $S_{2,2}$，所以应该有

\[ S_{3,3} = A_{3,3} + S_{2,3} + S_{3,2} - S_{2,2} = 5 + 18 + 15 - 9 = 29. \]

---

查询公式 & 时间复杂度

• 查询公式

对于一次查询 $(x_1,y_1)$ 到 $(x_2,y_2)$ 范围内的子矩阵和，按下式计算：

\[\begin{aligned} &\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i,j}\\ =&pre[x_2][y_2]-pre[x_1-1][y_2]-pre[x_2][y_1-1]+pre[x_1-1][y_1-1]. \end{aligned}\]

因此公式

\[ pre_{x_2,\ y_2}-pre_{x_1-1,\ y_2}-pre_{x_2,\ y_1-1}+pre_{x_1-1,\ y_1-1} \]

可以概括为 绿 + 蓝 + 橙 + 黄 - (绿 + 蓝) - (绿 + 橙) + 绿 = 黄。

• 时间复杂度
  • 预处理：构造 $pre[i][j]$ 需要 $O(n \times m)$。
  • 查询：每次常数次访问 $pre$，$O(1)$，共 $Q$ 次故 $O(Q)$。

---