差分数组是原数组相邻元素的差值构成的辅助数组，定义为diff[0]=arr[0]、diff[i]=arr[i]−arr[i−1]（i>0），可将区间[l,r]加val操作优化为O(1)的两次端点修改：diff[l]+=val、diff[r+1]−=val。
差分数组是什么，为什么它能加速区间更新
差分数组不是新数据结构，而是对原数组做一次预处理：定义 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 ）。时间复杂度从 O(n) 降到 O(1)。
它适合「多次区间加/减 + 最后一次性查询全部值」的场景，比如统计每个位置被覆盖次数、求最终数组最大值等。不适合边更新边单点查——那得上线段树或树状数组。
手写差分数组类要注意的边界和初始化
最容易错的是 r+1 越界和初始化方式。差分数组长度必须是 n（不是 n+1），但更新时要检查 r+1 是否合法；否则越界写入会引发未定义行为。
-
diff数组应初始化为全 0，再根据原始arr构建：先赋diff[0] = arr[0]，再循环算diff[i] = arr[i] - arr[i-1] - 如果初始数组为空或长度为 0，直接返回空
diff，别硬算arr[-1] - 更新操作中，若
r == n-1，跳过diff[r+1]这步——没有第n个元素 - 还原原数组时，必须用
arr[0] = diff[0]开始，然后arr[i] = arr[i-1] + diff[i]，不能反着来
std::vector 实现差分更新的典型代码模板
下面是一个轻量、安全、可复用的封装：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
class DiffArray {
std::vector<long long> diff;
int n;
public:
DiffArray(int size) : n(size), diff(size, 0) {}
DiffArray(const std::vector<int>& arr) : n(arr.size()), diff(arr.size(), 0) {
if (n == 0) return;
diff[0] = arr[0];
for (int i = 1; i < n; ++i) {
diff[i] = (long long)arr[i] - arr[i-1];
}
}
void update(int l, int r, long long val) {
if (l >= n || r < 0 || l > r) return;
diff[l] += val;
if (r + 1 < n) diff[r + 1] -= val;
}
std::vector<long long> recover() const {
std::vector<long long> res(n, 0);
if (n == 0) return res;
res[0] = diff[0];
for (int i = 1; i < n; ++i) {
res[i] = res[i-1] + diff[i];
}
return res;
}
};
注意：这里用 long long 防止多次更新后整数溢出；update 前做了参数校验；recover() 是只读操作，不修改内部状态。
和线段树对比：什么时候不该用差分数组
差分数组快，但能力有限。一旦需求里出现以下任一情况，就得换方案：
- 需要在更新过程中频繁查某个位置的当前值（
arr[i]）——差分数组查单点要 O(n) - 区间更新不是“统一加减”，而是“赋值”“取 max/min”“乘法”等非线性操作
- 区间长度动态变化，或下标范围极大（比如 1e9），而实际更新点稀疏——这时离散化+线段树或动态开点更合适
- 既要区间更新，又要区间求和/最值——差分数组无法高效支持
差分数组真正的价值，在于把“一堆区间加法”压缩成两次 O(1) 操作，最后用一次 O(n) 扫描收尾。它不是万能加速器，而是特定模式下的最优解。
