前缀和数组是预处理原数组各前缀累加和的辅助数组，能o(1)查区间和，但要求原数组不可变；其核心为prefix[i] = a[0]+…+a[i−1]，查询[l,r]和用prefix[r+1]−prefix[l]。
什么是前缀和数组？它真能 O(1) 查区间和吗
能，但前提是数组不修改。前缀和本质是用 O(n) 预处理空间换时间：对原数组 a 构造新数组 prefix，其中 prefix[i] 表示 a[0] + a[1] + ... + a[i-1]（常用 1-indexed 定义），这样任意区间 [l, r] 的和就是 prefix[r+1] - prefix[l]。
注意：下标偏移极易出错。常见错误包括越界访问、漏减 1、混淆 0-indexed 和 1-indexed 场景。
- 若原数组长度为
n，prefix长度应为n+1，prefix[0] = 0 -
prefix[i]对应前i个元素（即a[0..i-1]），不是前i+1个 - 查询
[l, r]（0-indexed 闭区间）时，结果是prefix[r+1] - prefix[l]，不是prefix[r] - prefix[l-1]
C++ 实现细节：vector 初始化与循环边界
用 std::vector 最稳妥。别手写 new int[n+1] —— 容易忘 delete，且不支持自动扩容。
关键在初始化和递推：
vector<int> a = {1, 2, 3, 4, 5};
vector<int> prefix(a.size() + 1, 0); // 显式初始化 size+1 个 0
for (int i = 1; i <ul>
<li>循环变量 <code>i</code> 从 <code>1</code> 开始，到 <code>a.size()</code> 结束（含），对应 <code>prefix[1..n]</code>
</li>
<li>
<code>prefix[0]</code> 必须为 <code>0</code>，否则 <code>[0, r]</code> 查询会错</li>
<li>如果后续要频繁查，建议把构造逻辑封装成函数，避免重复写边界</li>
</ul>
<h3>遇到负数、大数怎么办？溢出风险在哪</h3>
<p>前缀和本身不关心正负，但累加过程可能溢出。C++ 中 <code>int</code> 通常为 32 位，最大约 2e9。若原数组元素绝对值大或长度超 1e5，<code>int</code> 很容易溢出。</p>
<ul>
<li>保守做法：统一用 <code>long long</code> 存 <code>prefix</code>，即使 <code>a</code> 是 <code>int</code>
</li>
<li>不要假设“数据小就没事”—— 竞赛题或线上日志统计常暗藏大值</li>
<li>若必须用 <code>int</code>，需提前检查：每步加法前判断 <code>prefix[i-1] > INT_MAX - a[i-1]</code>，但会拖慢速度，一般不推荐</li>
</ul>
<h3>为什么不能边改边查？替代方案有哪些</h3>
<p>原始前缀和不支持单点修改。一旦改了 <code>a[i]</code>，从 <code>i+1</code> 开始所有 <code>prefix[j]</code> 都得重算，退化为 <code>O(n)</code>。</p>
<p>真需要动态更新，就该换结构：</p>
<ul>
<li>单点改 + 区间查 → 用 <code>std::vector</code> 配合 <code>std::partial_sum</code> 重算整个前缀和（适合修改极少）</li>
<li>频繁修改 + 查询 → 改用树状数组（<code>BIT</code>）或线段树，两者都支持 <code>O(log n)</code> 修改与查询</li>
<li>只查不改、内存极敏感 → 可考虑原地构造（复用 <code>a</code> 数组），但牺牲可读性，不推荐初学使用</li>
</ul>
<p>前缀和的简洁性建立在「静态」前提上；一旦这个前提松动，就得立刻评估是否还值得用它。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
