前缀和数组是存储原数组前i个元素累加和的辅助数组，能O(1)查区间和；因其查询仅需一次减法prefix[r+1]−prefix[l]，且prefix长度为n+1、prefix[0]=0以统一处理边界。
什么是前缀和数组，它为什么能 O(1) 查区间和
前缀和数组本质是一个辅助数组 prefix，其中 prefix[i] 存储原数组 nums[0..i-1] 的累加和（即前 i 个元素和）。这样，查询 [l, r] 区间和就变成 prefix[r+1] - prefix[l] —— 一次减法，天然 O(1)。
注意：标准实现中 prefix 长度为 n+1，且 prefix[0] = 0。这是为了统一处理左边界为 0 的情况，避免特判。
C++ 实现时最容易错的三个索引细节
写错索引是前缀和出 bug 的最常见原因，尤其在查询阶段：
-
prefix[i]表示前 i 个元素（nums[0]到nums[i-1]）之和，不是前 i+1 个 - 构建时循环应为
for (int i = 1; i ，用 <code>prefix[i] = prefix[i-1] + nums[i-1] - 查询
[l, r]（闭区间，0-indexed）时，结果是prefix[r+1] - prefix[l]，不是prefix[r] - prefix[l-1]（后者易越界且逻辑错）
完整可运行的 C++ 源码（含边界检查与注释）
#include <iostream>
#include <vector>
using namespace std;
<p>class PrefixSum {
private:
vector<long long> prefix; // 用 long long 防止 int 溢出</p><p>public:
PrefixSum(const vector<int>& nums) : prefix(nums.size() + 1, 0) {
for (int i = 1; i <= nums.size(); ++i) {
prefix[i] = prefix[i-1] + nums[i-1];
}
}</p><pre class="brush:php;toolbar:false;">// 查询 [l, r] 闭区间和，0-indexed；不检查 l/r 合法性，调用方需保证 0 <= l <= r < nums.size()
long long query(int l, int r) const {
return prefix[r + 1] - prefix[l];
}};
立即学习“C++免费学习笔记（深入）”；
int main() {
vector
cout << ps.query(1, 3) << endl; // 输出 2+3+4 = 9 cout << ps.query(0, 4) << endl; // 输出 15 cout << ps.query(2, 2) << endl; // 输出 3
}
什么时候不该用前缀和？两个现实约束
前缀和不是万能的：
- 原数组不可变是前提。一旦有单点修改（如
nums[i] += x），整个prefix从 i+1 开始都要更新 —— 退化为 O(n)，此时应考虑fenwick tree或segment tree - 空间开销固定为 O(n)。对内存极度敏感或数据流式到达（无法预知长度）的场景，前缀和不适用
另外，如果只是偶尔查一两次区间和，构建前缀和的 O(n) 预处理反而得不偿失。
