<p>差分数组是一种手动维护的技巧，用于高效处理区间增减操作；其核心是定义diff[i] = arr[i] - arr[i-1]（i > 0），使区间[l, r]加v仅需O(1)修改diff[l]和diff[r+1]，最后通过前缀和还原原数组。</p>
差分数组是什么，为什么用它
差分数组不是 C++ 标准库里的现成类型，而是一种手动维护的技巧，用来高效处理「区间增减」操作。比如你要对 arr[2..5] 每个元素加 3，朴素做法是循环加，O(n)；用差分数组，只要改两个位置，O(1) 完成更新，最后再做一次前缀和还原。
核心思想：定义 diff[i] = arr[i] - arr[i-1]（i > 0），则 arr[i] = diff[0] + diff[1] + ... + diff[i]。所以区间 [l, r] 加 v，只需：diff[l] += v，若 r+1 则 <code>diff[r+1] -= v。
如何手写一个差分数组类
别依赖第三方库，自己封装最可控。关键点是：初始化时拷贝原数组并构造差分，提供 update(l, r, v) 和 getArray() 方法。
-
diff数组长度和原数组相同，diff[0] = arr[0]，其余diff[i] = arr[i] - arr[i-1] -
update必须检查边界：if (l >= 0) diff[l] += v;，if (r + 1 -
getArray()返回新数组（不破坏差分结构），通过累加diff得到结果
示例片段：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
class Difference {
vector<int> diff;
public:
Difference(const vector<int>& arr) : diff(arr.size()) {
diff[0] = arr[0];
for (int i = 1; i < arr.size(); ++i)
diff[i] = arr[i] - arr[i-1];
}
void update(int l, int r, int v) {
if (l < 0 || r >= diff.size()) return;
diff[l] += v;
if (r + 1 < diff.size()) diff[r + 1] -= v;
}
vector<int> getArray() const {
vector<int> res(diff.size());
res[0] = diff[0];
for (int i = 1; i < diff.size(); ++i)
res[i] = res[i-1] + diff[i];
return res;
}
};常见错误：越界、忘记还原、误当原数组用
实际写的时候，这三个坑占了八成问题：
- 更新时没判
r + 1是否越界，导致diff[r+1]访问非法内存 —— 一定加if (r + 1 < diff.size()) - 多次
update后直接打印diff，以为那就是结果 ——diff不是最终数组，必须调用getArray()或手动前缀和还原 - 把差分数组当成原始数组传给其他函数（比如排序、查找），逻辑全错 —— 差分数组只服务区间更新，业务逻辑仍要基于还原后的数组
性能与适用场景提醒
差分数组快，但只在「大量区间修改 + 少量查询」时才有意义。如果每次更新后都要立刻查某个位置的值，不如直接用线段树或 Fenwick Tree。
- 空间复杂度 O(n)，时间上单次更新 O(1)，还原整个数组 O(n)
- 不支持单点修改（除非转成区间长度为 1 的更新）
- 不能高效查区间和 —— 差分本身不维护区间和信息，得先还原再求和，O(n) 起步
- 整数运算没问题，浮点数也行，但注意精度累积误差
真正容易被忽略的是：差分数组本质是“延迟应用”的中间表示，它的价值完全取决于你是否批量更新后再统一还原。零散改、零散查，反而更慢。
