基本概念
- 前缀和的定义：在C++算法与数据结构领域，前缀和是一种优化时间复杂度的有效手段，尤其适用于频繁查询数组区间和的场景。它通过预先计算“前缀累积和”，将原本使用for循环枚举O(n)的时间复杂度压缩至O(1)，是一种高频使用的优化技巧。
-
数学表示：
1. 基础数学符号定义
假设存在原数组：A=[a1,a2,a3,…,an]（下标从 1 开始，便于理解）
-
定义前缀和数组：S=[s0,s1,s2,…,sn]（通常令 s0=0，作为边界条件，简化计算）
-
2. 前缀和的递推公式（核心）
前缀和数组的每个元素满足：
si={0si−1+aii=0i≥1
展开后也可以表示为：
si=∑k=1iak=a1+a2+…+ai
- 核心思想：空间换时间，预处理后实现O(1)区间查询
一维前缀和
- 构建方法：线性遍历原数组，递推计算 #include<iostream>
using namespace std;int a[110], preSum[110];
//下标 1 2 3 4 5
//a[] 2 4 6 8 10
//ps[] 2 6 12 20 30
int main() {
//n个元素，m次查询，每次查询[l,r]的元素之和
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
//前i项和=前i-1项和+第i项
preSum[i] = preSum[i – 1] + a[i];//O(n)
}int m; cin >> m;
while (m–) {
int l, r; cin >> l >> r;
int sum = 0;
//for (int i = l; i <= r; i++) sum += a[i];//O(n)
sum = preSum[r] – preSum[l – 1];//o(1)
cout << sum << endl;
}return 0;
} - 查询区间和：sum[l..r] = S[r+1] – S[l]
- 应用场景：固定数组频繁区间求和（如子数组和统计）
二维前缀和
推导步骤：从 “拆分面积” 到核心公式
步骤 1：直观拆解矩形面积（初步思路）
要计算 S[i][j]（(1,1) 到 (i,j) 的矩形和），我们可以先尝试用一维前缀和的思路拆分：
- 先看 “前 i−1 行所有元素的和”：即 S[i−1][j]（(1,1) 到 (i−1,j) 的矩形和）；
- 再加上 “第 i 行前 j 个元素的和”：即一维前缀和 ∑k=1jA[i][k]。
此时初步表达式：S[i][j]=S[i−1][j]+∑k=1jA[i][k]
但这个表达式还不够 “二维”—— 我们需要把 “第 i 行前 j 个元素的和” 也用二维前缀和表示，避免重复计算。
步骤 2：发现重复区域，引入补偿思想
换一种拆分方式：把 (1,1) 到 (i,j) 的矩形拆分为几部分（如下图逻辑）：
步骤 3：推导核心递推公式
根据上述拆分逻辑，用前缀和符号替换 “区域”：
- 区域 1 = S[i−1][j]（上侧矩形和）；
- 区域 2 = S[i][j−1]（左侧矩形和）；
- 区域 3 = S[i−1][j−1]（重叠区域和）；
- 区域 4 = A[i][j]（当前元素）。
因此得到二维前缀和的核心递推公式：
S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+A[i][j]
综上可得实现代码如下：
#include<iostream>
using namespace std;
int a[110][110], preSum[110][110];
int main() {
//n个元素，m次查询，每次查询lx,ly和rx,ry围成的矩阵和
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
//1,1点到i,j点围成矩阵和-二维前缀和
preSum[i][j] = preSum[i – 1][j] + preSum[i][j – 1] – preSum[i – 1][j – 1] + a[i][j];
}
}
int k; cin >> k;
while (k–) {
//求lx,ly和rx,ry围成的矩阵和
int lx, ly, rx, ry; cin >> lx >> ly >> rx >> ry;
int sum = 0;
//for()
// for()
//二维前缀和求矩阵和
sum = preSum[rx][ry] – preSum[lx – 1][ry] – preSum[rx][ly – 1] + preSum[lx – 1][ly – 1];//O(1)
cout << sum << endl;
}
return 0;
}
差分与前缀和的互逆性
- 差分数组定义：d[i] = a[i] – a[i-1]（i ≥ 1）
- 前缀和恢复原数组：对差分数组求前缀和
- 应用：区间增减操作（如批量对[l,r]加k）转化为差分数组单点修改
常见应用场景
- 快速统计固定数组的区间和/子矩阵和
- 结合哈希表优化特定问题（如寻找和为k的子数组）
- 动态维护离线查询（如多次区间和请求）
复杂度分析
- 预处理时间：O(n)（一维）、O(mn)（二维）
- 查询时间：O(1)
- 空间复杂度：O(n)（一维）、O(mn)（二维）
实战例题
洛谷 1115. 最大子段和（一维前缀和）
题解如下：
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N], preSum[N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
preSum[i] = preSum[i – 1] + a[i];
}
int maxx = -0x3f3f3f3f;
//枚举所有的子段（连续一段区间）
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
//求解子段[l,r]的和
int sum = preSum[r] – preSum[l – 1];
if (sum > maxx) maxx = sum;
}
}
cout << maxx << endl;
return 0;
}
信息学奥赛一本通（1224：最大子矩阵）（二维前缀和）
以下为题解：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], s[N][N];
//s[i][j]代表1,1点到i,j点围成的矩形的元素和（二维前缀和）
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
//二维前缀和的递推式
s[i][j] = s[i – 1][j] + s[i][j – 1] – s[i – 1][j – 1] + a[i][j];
}
}
int mx = -0x3f3f3f3f;
//先枚举左上角点
for (int lx = 1; lx <= n; lx++) {
for (int ly = 1; ly <= n; ly++) {
//枚举右下角点
for (int rx = lx; rx <= n; rx++) {
for (int ry = ly; ry <= n; ry++) {
//求左上角点lx,ly和右下角点rx,ry围成的矩形的元素之和（矩阵和）
int sum = s[rx][ry] – (s[lx – 1][ry] + s[rx][ly – 1] – s[lx – 1][ly – 1]);
mx = max(mx, sum);
}
}
}
}
cout << mx << endl;
return 0;
}
注意事项
- 明确下标规则（0/1-based），保持递推、查询公式一致，避免l-1等操作越界，推荐 1-based 简化边界处理；
- 防范数据溢出，二维前缀和风险更高，大数值 / 高维度场景前缀和统一用long long类型；
- 原数组无需保留时，用原地前缀和优化空间，将空间复杂度降至 O (1)；
- 仅适用于静态数组，需频繁修改元素并查询区间和时，替换为线段树 / 树状数组。
