第 02 课前缀和

学习目标：理解一维前缀和“整体减去多余部分”的思想；能够写出区间和、区间异或和与前缀计数；知道前后缀最值的使用边界。

一、前缀和是什么

前缀和可以简单理解为“数列的前 \(n\) 项的和”，是一种重要的预处理方式。它先用 \(O(n)\) 时间把从左端开始的累计结果存起来，再把多次区间查询优化到 \(O(1)\)。

一句话理解：preSum[i] 表示从第 \(1\) 项到第 \(i\) 项的总和。

二、前缀和的计算

1. 定义

给定一维数组 \(a_1,a_2,\dots,a_n\)，定义前缀和：

\[ preSum_i=\sum_{k=1}^{i}a_k,\qquad 1\le i\le n. \]

即：

\[ preSum_1=a_1 \]

\[ preSum_2=a_1+a_2 \]

\[ preSum_3=a_1+a_2+a_3 \]

\[ \dots \]

\[ preSum_n=a_1+a_2+a_3+\dots+a_n. \]

2. 两种递推写法

写法	边界条件	递推公式	特点
基础写法	\(preSum_1=a_1\)	\(preSum_i=preSum_{i-1}+a_i,\ i=2,\dots,n\)	第 \(1\) 项需要单独处理
推荐写法	\(preSum_0=0\)	\(preSum_i=preSum_{i-1}+a_i,\ i=1,\dots,n\)	所有位置统一处理

基础写法代码：

// 前缀和（基础写法）
int preSum[N + 1] = {};

preSum[1] = a[1];
for (int i = 2; i <= n; i++) {
    preSum[i] = preSum[i - 1] + a[i];
}

实际竞赛中更推荐空出第 \(0\) 项，令 \(preSum_0=0\)：

// 前缀和（推荐写法）
long long preSum[N + 1] = {};  // preSum[0] 默认为 0

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

为什么推荐：因为 \(preSum_1=preSum_0+a_1\)，第 \(1\) 项无需特判，后续区间公式也能统一使用。数组元素与总和较大时，应使用 long long。

三、用前缀和求区间和

1. 思路来源：整体减去多余部分

若每次查询区间 \([L,R]\) 都从 \(L\) 加到 \(R\)，查询次数多时会很慢。前缀和 preSum[R] 包含 \([1,R]\) 的全部元素，其中多出来的部分恰好是 \([1,L-1]\)。

1 <--- preSum[L - 1] ----> L - 1   L <----- sum[L, R] -----> R
└────────────────────────────┘     └─────────────────────────┘
└────────────────────────────────────────────────────────────┘
1 <------------------------ preSum[R] ---------------------> R

所以：

\[ [1,R]=[1,L-1]+[L,R] \]

\[ [L,R]=[1,R]-[1,L-1]. \]

本质思想：整体减去多余部分。

2. 公式推导

已知：

\[ preSum_i=\sum_{k=1}^{i}a_k. \]

因此：

\[ preSum_R=a_1+a_2+\dots+a_{L-1}+a_L+\dots+a_R, \]

\[ preSum_{L-1}=a_1+a_2+\dots+a_{L-1}. \]

两式相减，前面的 \(a_1\) 到 \(a_{L-1}\) 抵消，得到：

\[ \sum_{k=L}^{R}a_k=preSum_R-preSum_{L-1},\qquad 1\le L\le R\le n. \]

当 \(L=1\) 时，\(preSum_{L-1}=preSum_0=0\)，公式仍然成立。

3. 代码实现

// 区间和 [L, R]
long long rangeSum(int L, int R) {
    return preSum[R] - preSum[L - 1];
}

// 多次询问
int q;
cin >> q;

while (q--) {
    int L, R;
    cin >> L >> R;
    cout << preSum[R] - preSum[L - 1] << '\n';
}

4. 复杂度

操作	时间复杂度	说明
预处理前缀和	\(O(n)\)	从左到右扫描一遍数组
一次区间和查询	\(O(1)\)	两次数组访问和一次减法
\(q\) 次查询总计	\(O(n+q)\)	适合静态数组、多次询问

四、前缀和的变式

前缀思想不局限于普通加法。只要某种运算能满足相应规律，并能把前面多余的信息消去或组合，就可以进行类似预处理。

（一）前缀异或和

1. 定义与计算

前缀异或和表示数列前 \(i\) 项的异或结果：

\[ preXor_i=\bigoplus_{k=1}^{i}a_k,\qquad 1\le i\le n. \]

设 \(preXor_0=0\)，则递推式为：

\[ preXor_i=preXor_{i-1}\oplus a_i. \]

// 前缀异或和
int preXor[N + 1] = {};  // preXor[0] = 0

for (int i = 1; i <= n; i++) {
    preXor[i] = preXor[i - 1] ^ a[i];
}

2. 区间异或和

异或满足自逆性：

\[ x\oplus x=0,\qquad x\oplus 0=x. \]

因此前缀中重复出现的 \([1,L-1]\) 会在再次异或时抵消：

\[ \bigoplus_{k=L}^{R}a_k=preXor_R\oplus preXor_{L-1}. \]

// 区间异或和 [L, R]
int rangeXor(int L, int R) {
    return preXor[R] ^ preXor[L - 1];
}

比较项	普通前缀和	前缀异或和
递推	`preSum[i] = preSum[i - 1] + a[i]`	`preXor[i] = preXor[i - 1] ^ a[i]`
区间查询	`preSum[R] - preSum[L - 1]`	`preXor[R] ^ preXor[L - 1]`
抵消依据	减去相同前缀	`x ^ x = 0`

注意：C++ 中 ^ 是按位异或，不是乘方。

（二）前缀最值

1. 前缀最大值与最小值

\[ preMax_i=\max_{1\le k\le i}a_k,\qquad preMax_i=\max(preMax_{i-1},a_i). \]

\[ preMin_i=\min_{1\le k\le i}a_k,\qquad preMin_i=\min(preMin_{i-1},a_i). \]

#include <algorithm>
#include <climits>

// 前缀最大值
long long preMax[N + 1];
preMax[0] = LLONG_MIN;

for (int i = 1; i <= n; i++) {
    preMax[i] = max(preMax[i - 1], a[i]);
}

// 前缀最小值
long long preMin[N + 1];
preMin[0] = LLONG_MAX;

for (int i = 1; i <= n; i++) {
    preMin[i] = min(preMin[i - 1], a[i]);
}

2. 为什么不能直接求任意区间最值

最值没有逆运算。已知：

\[ preMax_R=\max_{1\le k\le R}a_k, \]

\[ preMax_{L-1}=\max_{1\le k\le L-1}a_k, \]

无法从中去掉 \([1,L-1]\) 对最大值的影响，因此不能像前缀和一样得到任意区间 \([L,R]\) 的最大值。

普通前缀最值只能 \(O(1)\) 查询前缀 \([1,R]\) 的最值；任意区间最值需要后续学习 ST 表、线段树等结构。

负数边界：最大值初始值不能随便写 0。当数组全为负数时，应使用 LLONG_MIN；最小值对应使用 LLONG_MAX。

五、对应的后缀版本总结

前缀从左到右预处理；后缀从右到左预处理。它们思想完全对称：预处理 \(O(n)\)，查询 \(O(1)\)。

类型	前缀边界与递推	后缀边界与递推	可查询内容
和	`preSum[0] = 0`；`preSum[i] = preSum[i - 1] + a[i]`	`sufSum[n + 1] = 0`；`sufSum[i] = sufSum[i + 1] + a[i]`	前缀、后缀与任意区间和
异或	`preXor[0] = 0`；`preXor[i] = preXor[i - 1] ^ a[i]`	`sufXor[n + 1] = 0`；`sufXor[i] = sufXor[i + 1] ^ a[i]`	前缀、后缀与任意区间异或
最值	从左向右取 `max/min`	从右向左取 `max/min`	仅前缀或后缀最值

（一）后缀和

\[ sufSum_i=\sum_{k=i}^{n}a_k \]

\[ sufSum_{n+1}=0, \quad sufSum_i=sufSum_{i+1}+a_i. \]

// 后缀和
long long sufSum[N + 2] = {};

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

// 区间和 [L, R]
long long rangeSum(int L, int R) {
    return sufSum[L] - sufSum[R + 1];
}

（二）后缀异或和

\[ sufXor_i=\bigoplus_{k=i}^{n}a_k \]

\[ sufXor_{n+1}=0,\quad sufXor_i=sufXor_{i+1}\oplus a_i. \]

// 后缀异或和
int sufXor[N + 2] = {};

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

// 区间异或和 [L, R]
int rangeXor(int L, int R) {
    return sufXor[L] ^ sufXor[R + 1];
}

（三）后缀最值

\[ sufMax_i=\max_{i\le k\le n}a_k,\qquad sufMin_i=\min_{i\le k\le n}a_k. \]

#include <algorithm>
#include <climits>

// 后缀最大值与后缀最小值
long long sufMax[N + 2], sufMin[N + 2];
sufMax[n + 1] = LLONG_MIN;
sufMin[n + 1] = LLONG_MAX;

for (int i = n; i >= 1; i--) {
    sufMax[i] = max(sufMax[i + 1], a[i]);
    sufMin[i] = min(sufMin[i + 1], a[i]);
}

注意：后缀最值同样没有逆运算，只能 \(O(1)\) 查询后缀 \([i,n]\) 的最值，不能由两个后缀最值得到任意区间最值。

六、前缀和的应用：前缀计数

1. 定义

若只关心固定元素 \(x\) 在数组前 \(i\) 项中出现的次数，可定义前缀计数：

\[ preCnt_i=\sum_{k=1}^{i}[a_k=x]. \]

其中 \([a_k=x]\) 是指示函数：条件成立时为 \(1\)，不成立时为 \(0\)。

\[ preCnt_0=0,\qquad preCnt_i=preCnt_{i-1}+[a_i=x]. \]

// 前缀计数：统计元素 x
int preCnt[N + 1] = {};

for (int i = 1; i <= n; i++) {
    preCnt[i] = preCnt[i - 1] + (a[i] == x);
}

2. 查询区间内元素 x 的出现次数

\[ \sum_{k=L}^{R}[a_k=x]=preCnt[R]-preCnt[L-1]. \]

// 区间 [L, R] 中元素 x 的出现次数
int countX(int L, int R) {
    return preCnt[R] - preCnt[L - 1];
}

3. 常见建模

原问题	构造方式	查询结果
区间内偶数个数	偶数记 \(1\)，否则记 \(0\)	前缀计数的差
区间内正数个数	正数记 \(1\)，否则记 \(0\)	前缀计数的差
区间内及格人数	成绩达标记 \(1\)，否则记 \(0\)	前缀计数的差
区间内字符 `A` 的次数	字符为 `A` 记 \(1\)，否则记 \(0\)	前缀计数的差

若要查询多个不同元素的出现次数，可以为每个元素开一条前缀计数数组；也可以记录每个元素的出现位置并二分查询。

七、方法、套路与策略总结

1. 区间和标准套路

数组静态、区间询问多：优先考虑前缀和。
统一使用 1-based 下标，并设置 preSum[0] = 0。
建表：preSum[i] = preSum[i - 1] + a[i]。
查询：preSum[R] - preSum[L - 1]。
手算检查 \([1,1]\)、\([1,n]\)、单点区间和内部区间。

2. 变式迁移套路

想要右侧信息：从右到左建立后缀数组。
区间计数：先把条件变为 \(0/1\)，再求前缀和。
区间异或：把加法/减法替换为 ^，利用 \(x\oplus x=0\)。
左侧/右侧最优值：建立前缀最值与后缀最值。
前缀最值不能直接查询任意区间最值。

3. 常见错误

错误	后果	改正
写成 `preSum[R] - preSum[L]`	漏掉第 \(L\) 项	使用 `preSum[R] - preSum[L - 1]`
忘记 `preSum[0] = 0`	\(L=1\) 时需特判或越界	数组多开一位，统一处理
总和使用 `int`	累加溢出	使用 `long long`
把 `^` 当作乘方	得到按位异或结果	C++ 中 `^` 只表示异或
最值初值写 `0`	全负数组出错	使用 `LLONG_MIN` / `LLONG_MAX`
数组频繁修改仍用前缀和	每次修改需 \(O(n)\) 重建	后续学习树状数组、线段树

第 02 课 前缀和

一、前缀和是什么

二、前缀和的计算

1. 定义

2. 两种递推写法

三、用前缀和求区间和

1. 思路来源：整体减去多余部分

2. 公式推导

3. 代码实现

4. 复杂度

四、前缀和的变式

（一）前缀异或和

1. 定义与计算

2. 区间异或和

（二）前缀最值

1. 前缀最大值与最小值

2. 为什么不能直接求任意区间最值

五、对应的后缀版本总结

（一）后缀和

（二）后缀异或和

（三）后缀最值

六、前缀和的应用：前缀计数

1. 定义

2. 查询区间内元素 x 的出现次数

3. 常见建模

七、方法、套路与策略总结

1. 区间和标准套路

2. 变式迁移套路

3. 常见错误

第 02 课前缀和