前缀和算法详解
前缀和是一种通过预处理将区间查询复杂度降至 O(1) 的技术。核心在于构建累加数组，利用 dp[i] = dp[i-1] + nums[i] 快速计算任意区间的和。本文涵盖一维与二维前缀和模板，并延伸至哈希表结合的前缀和应用场景，如寻找中心下标、除自身以外乘积、和为 K 的子数组及矩阵区域和等问题。
DP34.【模板】一维前缀和
题目描述：给定一个数组，多次询问某个区间的元素和。
暴力解法 vs 前缀和
暴力解法每次询问都遍历区间，时间复杂度为 O(n*q)。而使用前缀和预处理后，单次查询只需 O(1)，总复杂度降为 O(q+n)。
实现思路
第一步是预处理前缀和数组。dp[i] 表示 [1, i] 区间内所有元素的和。递推公式很简单：
dp[i] = dp[i - 1] + arr[i]
第二步是利用前缀和数组快速计算区间和。当询问区间为 [l, r] 时，区间和等于 dp[r] - dp[l - 1]。
注意：C++ 中
vector<int> dp(n + 1)默认初始化为 0，因此dp[0]也是 0，这正好符合边界条件。
代码实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
// 输入原始数组，下标从 1 开始方便处理
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 预处理前缀和数组，使用 long long 防止溢出
vector<long long> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - ] + arr[i];
}
(q--) {
l, r;
cin >> l >> r;
cout << dp[r] - dp[l - ] << endl;
}
;
}
