算法基础：前缀和如何优化区间与子矩阵查询
在处理大量数据查询时，前缀和往往能带来立竿见影的性能提升。无论是处理一维数组的区间求和，还是解决二维矩阵的子矩阵问题，前缀和都能通过预处理将时间复杂度从线性降低到常数级别，彻底改变问题的解决方式。
核心思想
前缀和与差分的核心在于预处理。它用空间换取时间，在暴力枚举的过程中快速给出查询结果。
简单来说，前缀和就是快速求出数组中某一段区间的和，单次查询的时间复杂度为 O(1)。
一维前缀和
原理说明
假设我们有一个数组 a，定义前缀和数组 f，其中 f[i] 表示区间 [1, i] 中所有元素的和。
递推公式很简单：
f[i] = f[i - 1] + a[i]
当我们需要查询区间 [l, r] 的和时，直接利用前缀和数组相减即可：
sum(l, r) = f[r] - f[l - 1]
如果不使用前缀和，每次查询都需要遍历区间，时间复杂度是 O(n)，如果查询次数 q 很大，总复杂度会达到 O(n*q)，很容易超时。而使用前缀和后，预处理 O(n)，查询 O(1)，总复杂度降为 O(n + q)。
代码实现
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, q;
LL a[N];
LL f[N]; // 前缀和数组
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
// 处理前缀和
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + a[i];
}
(q--) {
l, r;
cin >> l >> r;
cout << f[r] - f[l - ] << endl;
}
;
}
