差分数组的核心作用是高效处理频繁区间增减、最终只查询单点值的问题；通过构造差分数组d使a[i]为d[0..i]前缀和，将区间[l,r]加v操作优化为d[l]+=v、d[r+1]-=v两个o(1)操作。
差分数组的核心作用是啥
它专治「频繁对区间做加减，最后只查单点值」的场景。比如给数组 a[0..n-1] 反复执行「把 a[l] 到 a[r] 都加 v」，暴力每次循环更新是 O(n)，差分能把单次更新压到 O(1)。
原理很简单：构造一个新数组 d，让原数组 a[i] = d[0] + d[1] + ... + d[i]（即 d 是 a 的差分）。那么「a[l..r] 加 v」就变成：d[l] += v，d[r+1] -= v（前提是 r+1 ）。
怎么写一个安全可用的差分类
别直接手写裸数组，容易越界或漏还原。用 std::vector 封装更稳：
class DiffArray {
std::vector<int> d;
public:
explicit DiffArray(size_t n) : d(n + 1, 0) {} // 多开1位，防 r+1 越界
void add(int l, int r, int v) {
if (l > r || l < 0 || r >= d.size() - 1) return;
d[l] += v;
if (r + 1 < d.size()) d[r + 1] -= v;
}
std::vector<int> getArray() const {
std::vector<int> a(d.size() - 1);
int sum = 0;
for (size_t i = 0; i < a.size(); ++i) {
sum += d[i];
a[i] = sum;
}
return a;
}
};
注意几个坑：
立即学习“C++免费学习笔记（深入）”；
-
d长度必须是n + 1，否则d[r+1]在r == n-1时越界 -
add()里要检查l、r合法性，C++ 不自动做边界判断 - 差分本身不支持「实时查单点」，必须调用
getArray()或自己手动前缀和还原——很多人以为d[i]就是当前值，这是错的
什么时候不该用差分数组
差分不是万能加速器，用错反而更慢：
- 如果操作以「单点修改 + 区间查询」为主（比如求
a[l..r]和），该上std::partial_sum或线段树，别硬套差分 - 如果更新次数极少（n > 1e6），差分的前缀和还原成本（
O(n)）可能比暴力更新还重 - 如果要支持「区间乘」「区间赋值」这类非线性操作，差分失效——它只对「加减」可叠加
- 浮点数场景慎用，累积误差会放大；整数溢出也要自己兜底，
int不够就换long long
和线段树、树状数组比有啥区别
差分最轻量，但能力也最窄：
- 线段树支持任意区间更新 + 任意区间查询（和/最值/异或等），但代码长、常数大；差分只支持「区间加 + 全量还原」
- 树状数组也能做区间加 + 单点查，但需要两个树维护，理解成本高；差分逻辑直白，适合快速验证想法
- 性能上：差分更新
O(1)，还原O(n)；树状数组单次更新/查询都是O(log n)；线段树同理，但常数约是树状数组的 2–3 倍 - 实际选型看需求：只要最后输出整个数组，且全是加减，差分就是最简最优解
真正容易被忽略的是还原时机——很多人在循环里反复调用 getArray()，结果从 O(q + n) 退化成 O(q × n)。差分的价值，全系于「攒够所有更新再一次性还原」这个节奏上。
