前缀和算法详解与实战
前缀和是一种高效处理区间查询的预处理技巧。通过预先计算累积和,可以将单次查询的时间复杂度从 O(N) 降低到 O(1)。本文将深入讲解一维及二维前缀和的原理,并结合 LeetCode 经典题目展示其实际应用场景。
一维前缀和
核心思路
构建一个前缀和数组 dp,其中 dp[i] 表示原数组 arr 在 [1, i] 区间内所有元素的累加和。递推公式为:
dp[i] = dp[i-1] + arr[i]
利用该数组,可以在 O(1) 时间内求出任意区间 [l, r] 的和:
sum(l, r) = dp[r] - dp[l-1]
注意:为了简化边界处理,通常将数组下标从 1 开始,并在初始化时预留 dp[0] = 0。
代码实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
// 使用 long long 防止溢出
vector<long long> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + arr[i];
}
(q--) {
l, r;
cin >> l >> r;
cout << dp[r] - dp[l - ] << endl;
}
;
}

