差分数组的核心原理是通过预处理构造辅助数组diff，其中diff[0]=arr[0]、diff[i]=arr[i]−arr[i−1]（i>0），将原数组区间[l,r]加val的操作转化为diff[l]+=val和diff[r+1]−=val两个o(1)操作。
差分数组的核心原理是什么
差分数组不是新数据结构，而是对原数组做一次预处理：定义 diff[i] = arr[i] - arr[i-1]（i > 0），diff[0] = arr[0]。这样，原数组的任意区间 [l, r] 加上 val，就变成只改两个位置：diff[l] += val，diff[r+1] -= val（前提是 r+1 ）。还原时只需一次前缀和：<code>arr[i] = diff[0] + ... + diff[i]。
它快在把 O(n) 的区间更新降为 O(1)，代价是 O(n) 的单次还原 —— 所以适合「多次区间修改 + 少量最终查询」场景，比如离线处理后一次性输出结果。
如何避免下标越界和边界错误
最常踩的坑是 r+1 越界导致写坏内存或未定义行为。C++ 中必须显式检查：
- 若使用
std::vector<int> diff(n)</int>，则r+1合法当且仅当r+1 - 更新时别写成
diff[r] -= val—— 这会错位影响后续还原 - 如果区间右端点
r可能等于n-1，那diff[r+1]就越界，直接跳过减操作
示例：
void addRange(int l, int r, int val) {
diff[l] += val;
if (r + 1 <h3>差分数组与线段树、树状数组怎么选</h3><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>
- 纯离线批量更新 → 差分数组，代码短、无额外空间开销、缓存友好
- 需要中间查询或复杂操作（如区间乘、历史版本）→ 上线段树
- 只需要单点更新 + 区间求和 → 树状数组更轻量，但区间加仍需两次单点更新（差分思想的变体）
注意：差分数组本身不维护原始数组，每次查询某位置值都得重算前缀和 —— 如果频繁查单点，不如直接用 std::vector 记录操作再统一 apply。
用 vector 实现时要注意什么
C++ 的 std::vector 默认初始化为 0，很适合差分数组这种“初始全零”的场景，但别忘了显式指定大小：
- 构造时写
vector<int> diff(n, 0)</int>，别依赖默认构造（可能未初始化） - 如果后续要 resize，记得同步更新
n变量，否则r+1 判断失效 - 不需要额外封装类 —— 简单函数 + raw vector 更快；但若逻辑分散，可封装
class DiffArray，把n和diff绑定
一个最小可用片段：
int n = 100000; vector<int> diff(n, 0); // 更新 [2,5] 加 3 diff[2] += 3; if (6 arr(n); arr[0] = diff[0]; for (int i = 1; i <p>真正容易被忽略的是：差分数组的“高效”完全依赖你控制好更新与还原的节奏 —— 混入实时查询或中途插入新更新，整个模型就崩了。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
