前缀和是一种数组预处理思想，定义prefix[i]为arr[0..i-1]的和（左闭右开），使区间[l,r]求和达o(1)；直接用std::partial_sum易因包含当前元素导致边界错误，应手动构建n+1长long long数组并设prefix[0]=0。
什么是前缀和，为什么不用 std::partial_sum 就容易出错
前缀和不是某个函数的代名词，而是一种**数组预处理思想**：让 prefix[i] 表示原数组 arr[0..i-1] 的和（左闭右开），这样后续任意区间 [l, r] 的和就能在 O(1) 拿到：prefix[r+1] - prefix[l]。很多人直接用 std::partial_sum 却忽略它默认是「包含当前元素」的累加，即 partial_sum(arr, arr+n, prefix) 会让 prefix[i] = arr[0]+...+arr[i]，这会导致区间查询时边界要反复 ±1，极易越界或漏项。
更稳妥的做法是手动构建长度为 n+1 的前缀数组，让 prefix[0] = 0，然后循环计算：
vector<long long> prefix(n + 1);
for (int i = 0; i <ul>
<li>必须开 <code>n+1</code> 长度，否则 <code>prefix[n]</code> 无法表示全部元素和</li>
<li>类型推荐 <code>long long</code>，避免 <code>int</code> 溢出（尤其数据量大或值本身大时）</li>
<li>
<code>prefix[0] = 0</code> 是关键锚点，不是可选项</li>
</ul>
<h3>二维前缀和怎么初始化，<code>dp[i][j]</code> 到底存哪块区域的和</h3>
<p>二维前缀和的定义是：<code>prefix[i][j]</code> 表示从 <code>(0,0)</code> 到 <code>(i-1,j-1)</code>（左上角为原点，不包含第 i 行、第 j 列）所有元素之和。这个定义才能让矩形查询公式干净统一：<code>prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]</code>。</p>
<p>初始化代码必须严格按此逻辑：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<pre class="brush:php;toolbar:false;">vector<vector long>> prefix(m + 1, vector<long long>(n + 1));
for (int i = 0; i <ul>
<li>二维数组也必须是 <code>(m+1) × (n+1)</code>，否则下标 <code>i+1</code>/<code>j+1</code> 必然越界</li>
<li>减掉 <code>prefix[i][j]</code> 是容斥关键，漏掉就会重复累加左上角子矩阵</li>
<li>如果原矩阵是 <code>vector<vector>></vector></code>，前缀数组务必升为 <code>long long</code> 类型</li>
</ul>
<h3>修改单点后还想快速查区间和？别硬套前缀和</h3>
<p>前缀和本质是静态结构——一旦构建完成，就不能高效支持单点更新。比如把 <code>arr[i]</code> 加了 5，你得把所有 <code>prefix[j]</code>（<code>j > i</code>）都重新算一遍，退化成 O(n)。这时候该换数据结构：</p>
<ul>
<li>需要单点改 + 区间查 → 用 <code>fenwick tree</code>（树状数组）或 <code>segment tree</code>（线段树）</li>
<li>
<code>fenwick tree</code> 更轻量，代码短，适合只做加法更新</li>
<li>如果还要支持区间更新（如整体加 x），<code>segment tree</code> 带 lazy 标记更合适</li>
<li>别试图在前缀和数组上“打补丁”，边界修正会迅速失控</li>
</ul>
<h3>LeetCode 上常见陷阱：负数、下标从 1 开始、输入是 vector 还是 array</h3>
<p>很多题（如 <code>subarray-sum-equals-k</code>）表面看能用前缀和，但实际要配合哈希表做“前缀和出现次数”统计，这时要注意：</p>
<ul>
<li>必须初始化哈希表含 <code>{0: 1}</code>，因为和为 0 的空前缀合法</li>
<li>题目给的数组下标常从 0 开始，但描述中区间可能说「第 1 到第 5 个数」，需立刻转成 0-based 理解</li>
<li>输入如果是 <code>vector<int>&</int></code>，别擅自改成裸指针操作；C++11 后用 <code>for (auto x : arr)</code> 更安全</li>
<li>遇到 <code>INT_MIN</code> 或大负数，累加过程可能溢出 <code>int</code>，强制用 <code>long long</code> 存前缀和</li>
</ul>
<p>最常被忽略的是：前缀和数组本身不解决“找子数组”问题，它只是工具；真正逻辑在怎么用差值匹配目标——这点一模糊，整个思路就偏到暴力去了。</p></long></vector>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
