前缀和算法原理与实战应用详解
一、一维前缀和
1. 核心思路
前缀和的核心在于预处理。通过构建一个数组,记录从起点到当前位置的累加值,这样任意区间的和就可以通过两次减法在 O(1) 时间内求得。
为了避免下标越界问题,通常让前缀和数组的下标从 1 开始,原数据从 0 或 1 开始映射。
公式:S[i] = S[i-1] + A[i]
区间 [l, r] 的和为:S[r] - S[l-1]
2. 代码实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
// 多开一个节点防止越界,下标从 1 开始
vector<long long> dp(n + 1);
int tmp = 0;
for (int i = 1; i <= n; i++) {
cin >> dp[i];
}
// 计算前缀和
for (int i = 1; i <= n; i++) {
dp[i] += dp[i - 1];
}
int l, r;
while (q--) {
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}










