前缀和数组适合多次查询、极少修改的静态场景，O(1)查询区间和；差分数组适合批量区间更新后一次性还原，O(1)更新；二者均不支持动态混合操作，此时需线段树或树状数组。
前缀和数组：用 vector 一次性预处理，查询 O(1)
前缀和本质是空间换时间，适合「多次单点查询、极少修改」的场景。核心就是让 prefix[i] 表示原数组 a[0..i-1] 的和（常用 1-indexed 风格避免边界判断）。
- 初始化时循环计算：
prefix[i] = prefix[i-1] + a[i-1]，注意下标对齐 - 查询区间
[l, r]（闭区间，0-indexed）和：直接用prefix[r+1] - prefix[l] - 别手抖写成
prefix[r] - prefix[l-1]——这是 1-indexed 写法，但 C++ 数组默认 0-indexed，混用会越界或漏元素 - 如果原数组会变，前缀和就失效了；此时不能边改边维护，得重算整个
prefix，复杂度退化为O(n)
vector<int> a = {1, 2, 3, 4, 5};
vector<int> prefix(a.size() + 1, 0);
for (int i = 1; i <= a.size(); i++) {
prefix[i] = prefix[i-1] + a[i-1];
}
// 查询 [1, 3]（0-indexed）即元素 2+3+4 = 9
int sum = prefix[4] - prefix[1]; // 15 - 1 = 14？不对！注意：a[1..3] 是索引 1,2,3 → 对应 prefix[4]-prefix[1] = 15-1 = 14，但 a[1]+a[2]+a[3]=2+3+4=9 → 错！
// 正确：a[1..3] 共 3 个元素，对应 prefix[4]-prefix[1] 实际是 a[0..3] - a[0..0] = a[1..3] ✅
// 所以只要定义清晰，就没问题。更安全写法：统一用 [l, r] 闭区间，返回 prefix[r+1]-prefix[l]
差分数组：用 vector 维护增量，区间更新 O(1)
差分数组 d 定义为：d[0] = a[0]，d[i] = a[i] - a[i-1]（i > 0）。它的价值在于：对原数组 a 的区间 [l, r] 加 val，只需改两个位置：
d[l] += val-
d[r+1] -= val（前提是r+1 < d.size()） - 之后通过一次前缀和还原就能得到最新
a：即a[i] = d[0] + d[1] + ... + d[i] - 频繁更新 + 最后一次性还原？用差分；频繁更新 + 中间穿插查询？得配合线段树或树状数组
- 常见错误：忘记检查
r+1越界，导致写到非法内存；或者还原时没从d做前缀和，而是误用原a数组参与计算
vector<int> a = {1, 2, 3, 4, 5};
vector<int> d(a.size(), 0);
d[0] = a[0];
for (int i = 1; i < a.size(); i++) {
d[i] = a[i] - a[i-1];
}
// 对 [1,3] 加 10 → a[1],a[2],a[3] 都 +10
d[1] += 10;
if (4 < d.size()) d[4] -= 10; // r+1 = 3+1 = 4
<p>// 还原 a
vector<int> new_a = d;
for (int i = 1; i < new_a.size(); i++) {
new_a[i] += new_a[i-1];
}
// new_a = {1,12,13,14,5}</p>前缀和 + 差分组合：解决「先批量更新、再批量查询」类问题
很多 OJ 题（比如洛谷 P3372 改编简化版）要求：给定 n 个数，执行 m 次区间加，最后输出每个位置的值。这时不用线段树，纯靠差分 + 前缀和就够了。
- 步骤固定三步：建差分数组 → 每次更新改两个点 → 最后做一遍前缀和还原
- 时间复杂度：
O(n + m)，远优于暴力更新的O(n×m) - 注意差分数组长度至少为
n+1，否则d[r+1]必越界；推荐初始化为vector<int> d(n + 1, 0) - 如果题目还要求中间查某个前缀和（比如「前 i 项和」），那就得在还原出最终
a后，再额外构建一层前缀和数组；不能直接对d做两次前缀和——那得到的是原数组的前缀和的前缀和，不是你要的
什么情况不能只用前缀和 / 差分？
当需求变成「边更新、边查询任意区间和」，例如：执行一次区间加，立刻问某区间和是多少——这时候差分数组无法直接回答，因为你还未还原；而还原一次要 O(n)，太慢。
立即学习“C++免费学习笔记（深入）”；
- 前缀和只支持静态查询，不支持高效更新
- 差分只支持高效更新，不支持高效动态查询
- 二者都是线性结构，没有分治或树形加速能力
- 真正需要「动态区间更新 + 动态区间查询」，得上
segment tree或Fenwick tree（树状数组），它们能同时做到O(log n)更新与查询 - 别硬套前缀和/差分去解动态混合题，调试半天发现 TLE 或 WA，大概率是模型选错了
实际写题时，先盯死操作类型：全是更新最后查？差分；全是查很少改？前缀和；更新和查穿插？别犹豫，直接写线段树。
