差分数组

差分数组存储相邻前缀状态之间的增量，而不是每个位置的绝对值。区间统一加上 $v$ 时，内部相邻元素同时增加，差值彼此抵消，只有左端加 $v$、右端后一位减 $v$ 的边界变化留下；最后一次前缀累积恢复全部元素。这个技巧本质上是离散微分与离散积分的互逆。

原数组 $[1,3,3,5]$ 的差分可写为 $[1,2,0,2]$。对区间 $[2,3]$ 加 $4$，修改 $d_2+=4$、$d_4-=4$，得到 $[1,6,0,-2]$；前缀恢复为 $[1,7,7,5]$。

差分适合离线积累大量区间更新，并在线性时间统一恢复，却不能在每次更新后立即回答任意区间查询，除非再配合 Fenwick 树或线段树。普通差分要求更新是可组合、可逆的加法作用；在一般交换幺半群上只有前缀聚合而未必存在差分。

差分连接离散导数与前缀积分：前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。是恢复操作，交换群公理库阿贝尔群Abelian group · Commutative group运算还满足交换律的群，通常用加法记号表达其叠加结构。提供加法逆元，数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。提供可寻址的有界坐标域。它支撑扫描线事件和区间更新批处理；二维差分可把矩形更新化为四个角点修改，在线场景则通过两个Fenwick 树公理库Fenwick 树Fenwick tree · Binary indexed tree用二进制最低位分解维护动态前缀聚合，支持单点更新与前缀查询的对数时间数据结构。实现区间加与前缀/区间和。前缀恢复也可用并行 scan 或按块顺序读取，但工作、深度和 I/O 必须在各自模型中另计。

差分数组并不是一般数据流摘要：它需要为每个端点保留可寻址槽位，并在最后完整扫描。数据流分位数公理库流式分位数摘要streaming quantiles · quantile sketch在单遍小空间中返回秩误差受控的近似分位数，而非数值距离近似。面对可能巨大或未知的值域，只用受限空间近似秩查询，通常显式带误差与失败概率；两者都“顺序处理更新”，却在存储假设、输出语义和保证类型上完全不同。