c++怎么实现前缀和与差分数组_c++ 区间频繁更新与查询优化【实战】

前缀和数组适合多次查询、极少修改的静态场景，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 a = {1, 2, 3, 4, 5};
vector 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 ）
• 之后通过一次前缀和还原就能得到最新 a：即 a[i] = d[0] + d[1] + ... + d[i]
• 频繁更新 + 最后一次性还原？用差分；频繁更新 + 中间穿插查询？得配合线段树或树状数组
• 常见错误：忘记检查 r+1 越界，导致写到非法内存；或者还原时没从 d 做前缀和，而是误用原 a 数组参与计算

vector a = {1, 2, 3, 4, 5};
vector 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
// 还原 a
vector 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}

前缀和 + 差分组合：解决「先批量更新、再批量查询」类问题

很多 OJ 题（比如洛谷 P3372 改编简化版）要求：给定 n 个数，执行 m 次区间加，最后输出每个位置的值。这时不用线段树，纯靠差分 + 前缀和就够了。

• 步骤固定三步：建差分数组 → 每次更新改两个点 → 最后做一遍前缀和还原
• 时间复杂度：O(n + m)，远优于暴力更新的 O(n×m)
• 注意差分数组长度至少为 n+1，否则 d[r+1] 必越界；推荐初始化为 vector d(n + 1, 0)
• 如果题目还要求中间查某个前缀和（比如「前 i 项和」），那就得在还原出最终 a 后，再额外构建一层前缀和数组；不能直接对 d 做两次前缀和——那得到的是原数组的前缀和的前缀和，不是你要的

什么情况不能只用前缀和 / 差分？

当需求变成「边更新、边查询任意区间和」，例如：执行一次区间加，立刻问某区间和是多少——这时候差分数组无法直接回答，因为你还未还原；而还原一次要 O(n)，太慢。

立即学习“C++免费学习笔记（深入）”；

• 前缀和只支持静态查询，不支持高效更新
• 差分只支持高效更新，不支持高效动态查询
• 二者都是线性结构，没有分治或树形加速能力
• 真正需要「动态区间更新 + 动态区间查询」，得上 segment tree 或 Fenwick tree（树状数组），它们能同时做到 O(log n) 更新与查询
• 别硬套前缀和/差分去解动态混合题，调试半天发现 TLE 或 WA，大概率是模型选错了

实际写题时，先盯死操作类型：全是更新最后查？差分；全是查很少改？前缀和；更新和查穿插？别犹豫，直接写线段树。