差分数组通过辅助数组记录变化量，将多次区间增减压缩为O(1)单点操作，更新总成本O(q)，还原O(n)；适用于区间加减为主、更新频繁、无需实时查询的场景。

差分数组不是靠“优化数组本身”来提速，而是用一个辅助数组记录变化量，把多次区间增减压缩成几个单点操作，最后一次性还原。它真正快的地方在于：不管做 10 次还是 1000 次区间加减，更新阶段始终是 o(1) 每次，总更新成本仅 o(q)，还原只需一次 o(n) 前缀和。

什么时候该用差分数组

只在满足以下组合时才推荐使用：

• 操作以「区间加减」为主（比如 [l, r] 全部 +5），不是单点赋值、乘法或取模
• 更新次数较多（q ≥ 数十次），而查询要么不查、要么只查最终结果或少数几个位置
• 不需要实时知道任意位置的当前值，也不需要动态查区间和、最值等
• 原数组长度 n 较大（如 1e5 以上），暴力遍历区间会明显拖慢

标准实现步骤（以 0-indexed 为例）

核心是三步：建差分数组 → 批量打标记 → 一次性还原

• 初始化差分数组：声明长度为 n+1 的数组（多开一位防越界），全初始化为 0；若已有原数组 arr，可跳过初始构建，直接进入更新
• 区间更新操作：对 [l, r] 加 val，执行 diff[l] += val；若 r+1
• 还原原数组：从左到右累加，arr[0] = diff[0]，arr[i] = arr[i−1] + diff[i]（i ≥ 1）；也可就地还原：for (int i = 1; i

实战中必须绕开的坑

很多性能问题其实来自误用，而非算法本身：

• 别在每次更新后都还原整个数组——反复调用前缀和会让复杂度退化成 O(q·n)
• 别用 int 存差分值，尤其当 val 大或操作多时，容易溢出；建议统一用 long long 或 int64_t
• 输入的 l、r 必须先校验是否在 [0, n−1] 范围内；r+1 越界时一定跳过减操作，否则写坏内存
• 不要把差分数组当成“实时数组”去读取中间状态——diff[i] 不代表 arr[i]，它只在还原后才有意义

小规模或特殊场景的替代方案

差分不是万能解，有些情况换别的结构更合适：

• 如果只更新 1–2 次，直接 for 循环改原数组反而更快，免去构造和还原开销
• 需要频繁单点查（比如每轮更新后立刻问第 k 个值），可边累加边停：sum = 0; for (int i = 0; i ≤ k; ++i) sum += diff[i]，O(k) 即得
• 要支持区间求和、最大值、历史版本回溯，就得换成树状数组或线段树
• 涉及等差数列区间填充（如 [l,r] 填入 a, a+d, a+2d…），需用「二阶差分」，不能套一维模板