算法基础:前缀和技巧与区间求优化
在算法设计与性能优化中,前缀和(Prefix Sum)是一种简单却极具威力的技巧。它通过预处理数据,将原本需要线性遍历的区间求和问题转化为常数时间的查询,实现了典型的'空间换时间'策略。无论是处理一维数组的区间累加,还是解决二维矩阵的子区域统计,掌握前缀和都能显著提升代码效率。
本文将深入探讨一维和二维前缀和的核心原理、实现细节及典型应用场景,帮助你理解这一基础算法如何在竞赛与工程实践中改变问题的复杂度格局。
一维前缀和
核心原理
对于静态数组的多次区间求和查询,暴力模拟每次遍历的时间复杂度高达 O(n*q),极易超时。前缀和通过预先计算每个位置之前的累加和,将单次查询降至 O(1)。
定义前缀和数组 f,其中 f[i] 表示原数组 a 从下标 1 到 i 的元素之和。递推公式如下:
f[i] = f[i - 1] + a[i]
当需要查询区间 [l, r] 的和时,利用容斥原理,结果即为:
sum(l, r) = f[r] - f[l - 1]
注意:通常为了处理边界情况方便,数组下标从 1 开始,且 f[0] 初始化为 0。
代码实现
#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;
}
;
}


