算法实战：一维与二维前缀和模板详解
25.【模板】前缀和
题目描述
给定一个长度为 n 的数组，进行 m 次区间求和查询。
解题思路
处理这类区间求和问题，暴力枚举每次查询的时间复杂度是 O(n)，总复杂度会达到 O(nm)，在数据量大时容易超时。利用前缀和思想，我们可以将预处理时间控制在 O(n)，之后每次查询只需 O(1)。
核心在于构建一个前缀和数组 dp，其中 dp[i] 表示原数组从下标 1 到 i 所有元素的累加和。这样，任意区间 [l, r] 的和就可以通过 dp[r] - dp[l-1] 快速得到。
递推公式很简单：
dp[i] = dp[i-1] + arr[i]
C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// nums 存储原始数据，ans 存储前缀和（注意下标偏移）
vector<long long> nums(n, 0);
vector<long long> ans(n + 1, 0);
for(int i = 0; i < n; i++) {
cin >> nums[i];
// 前缀和计算，ans[i+1] 对应 nums[0...i] 的和
ans[i + 1] = nums[i] + ans[i];
}
while(m--) {
int l, r;
cin >> l >> r;
// 区间 [l, r] 的和 = 前缀和[r] - 前缀和[l-1]
cout << ans[r] - ans[l - ] << endl;
}
;
}
