前言
在算法设计与优化中,前缀和是一种简单却强大的技巧,能够将复杂问题转化为高效计算。无论是处理一维数组的区间求和,还是解决二维矩阵的子矩阵问题,前缀和都能通过预处理将时间复杂度从线性降低到常数级别,彻底改变问题的解决方式。
从经典的最大子段和问题到实际应用中的'激光炸弹'场景,前缀和不仅展现了数学的优雅,更体现了算法思维的灵活性。本文将深入探讨一维和二维前缀和的原理与应用,揭示其如何通过'预谋'式的预处理,在竞赛与工程中成为改变游戏规则的关键。
前缀和
前缀和与差分的核心思想是预处理,可以在暴力枚举的过程中,快速给出查询的结果,从而优化时间复杂度。
是经典的用空间替换时间的做法。
前缀和: 快速求出数组中某一段区间和,时间复杂度为 O(1)。
1.1 一维前缀和
1.1.1 前缀和

算法原理:
- 暴力模拟实现,从指定的下标进行循环,时间复杂度为 O(n * q) 会超时
- 前缀和:
a. 先预处理出来一个前缀和数组
f[i] 表示:区间 [1, i] 中所有元素和
则
f[i] = f[i - 1] + a[i]b. 查询 [l, r] 区间和,则f[r] - f[l - 1]


参考代码:
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, q;
LL a[N];
LL f[N]; // 前缀和数组
{
cin >> n >> q;
( i = ; i <= n; i++) cin >> a[i];
( i = ; i <= n; i++) {
f[i] = f[i - ] + a[i];
}
(q--) {
l, r;
cin >> l >> r;
cout << f[r] - f[l - ] << endl;
}
;
}









