前缀和数组是存储原数组前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 溢出</long></p>
<p>public:
PrefixSum(const vector<int>& nums) : prefix(nums.size() + 1, 0) {
for (int i = 1; i <pre class="brush:php;toolbar:false;">// 查询 [l, r] 闭区间和，0-indexed；不检查 l/r 合法性，调用方需保证 0 <p>};</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div><p>int main() {
vector<int> nums = {1, 2, 3, 4, 5};
PrefixSum ps(nums);</int></p><pre class="brush:php;toolbar:false;">cout <p>}
</p>
什么时候不该用前缀和？两个现实约束
前缀和不是万能的：
- 原数组不可变是前提。一旦有单点修改（如
nums[i] += x），整个prefix从 i+1 开始都要更新 —— 退化为 O(n)，此时应考虑fenwick tree或segment tree - 空间开销固定为 O(n)。对内存极度敏感或数据流式到达（无法预知长度）的场景，前缀和不适用
另外，如果只是偶尔查一两次区间和，构建前缀和的 O(n) 预处理反而得不偿失。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
