差分数组的核心价值是将区间多次加减压缩为两次单点修改并用前缀和还原；其构造为d[0]=a[0]、d[i]=a[i]−a[i−1]（i≥1），长度n+1；关键性质是对a[l..r]加v只需d[l]+=v、d[r+1]−=v。
差分数组的核心价值在于：把对区间的多次加减操作，压缩成两次单点修改，再通过一次前缀和还原结果。它不直接处理原始数据，而是维护“变化量”，特别适合区间更新频繁、查询较少的场景——比如日志统计、资源配额调整、活动时段标记等。
理解差分数组的构造逻辑
给定原数组 A[0..n-1]，其差分数组 D[0..n] 定义为：
- D[0] = A[0]
- D[i] = A[i] - A[i-1]（i ≥ 1）
- 为方便区间操作，通常将 D 长度设为 n+1，末尾多一位用于边界控制
关键性质：对 A[l..r] 整体加 v，只需：
- D[l] += v
- D[r+1] -= v（前提是 r+1
这样，后续一次从左到右的前缀和计算（A[i] = D[0]+...+D[i]），就能自动把增量传播到整个区间。
实战步骤：三步完成高效批量修改
以「给 100 万个用户在 [1000, 5000]、[8000, 9999]、[200, 300] 三个时间段统一增加 5 点活跃值」为例：
- 初始化差分数组：创建长度为 10001 的 diff（覆盖 0~10000），全 0
-
批量打标（O(1) 每次）：
- diff[1000] += 5；diff[5001] -= 5
- diff[8000] += 5；diff[10000] -= 5（注意 9999+1=10000，合法）
- diff[200] += 5；diff[301] -= 5
- 一次性还原（O(n) 总耗）：遍历 diff 做前缀和，得到最终每个位置的增量值；再按需叠加到原数据或直接输出
边界与工程细节必须注意
- 索引越界防护：执行 diff[r+1] -= v 前，务必判断 r+1 ，否则跳过（右边界超出即无需抵消）
-
离散化适配海量稀疏区间：若实际操作的坐标范围极大（如 0~1e9），但只有几千个区间，就不要开大数组。改用 TreeMap
存键值对，只存非零差分点，再排序+扫描还原 - 支持负数与多次叠加：差分天然支持减法（v 为负）和任意顺序更新，所有修改互不干扰
- 空间换时间的真实代价：内存占用约等于原数组两倍（差分数组 + 还原结果），但远低于每次区间遍历的 O(k×len) 时间开销
什么情况下不该用差分数组？
当你的场景出现以下任一情况，应考虑替代方案（如线段树、树状数组）：
- 需要在修改过程中频繁单点查询某个位置当前值（差分必须还原才能查）
- 区间更新与单点/区间查询交替非常密集（差分的查询成本是 O(n)）
- 要支持区间最值、乘法更新、历史版本回溯等复杂操作
差分不是万能加速器，它是「写多读少、纯加减、静态范围」场景下的极简最优解。
