算法模板精讲：一维与二维前缀和
在处理区间求和问题时，如果涉及多次查询，暴力计算会导致超时。前缀和（Prefix Sum）是一种经典的预处理技巧，能将单次查询的时间复杂度从 O(N) 降低到 O(1)。本文将详细讲解一维和二维前缀和的核心逻辑、公式推导及代码实现。
一、一维前缀和
核心思路
假设我们有一个数组 arr，我们希望快速求出任意区间 [l, r] 内元素的和。
- 预处理：构建一个前缀和数组
dp。定义dp[i]为原数组下标1到i所有元素的累加和。- 递推公式：
dp[i] = dp[i - 1] + arr[i] - 注意：为了处理边界方便，通常将数组下标从 1 开始，
dp[0]设为 0。
- 递推公式：
- 查询：当需要计算区间
[l, r]的和时，利用容斥思想：- 区间和 =
dp[r] - dp[l - 1]
- 区间和 =
代码实现
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 使用 long long 防止求和溢出
vector<long long> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 预处理前缀和
vector<long long> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - ] + arr[i];
}
(m--) {
l, r;
cin >> l >> r;
cout << dp[r] - dp[l - ] << endl;
}
;
}
