差分数组(Difference Array)

差分数组(Difference Array)是一种与前缀和互为逆运算的辅助数组技巧。它记录原数组每个位置与前一位置的差值,使得对原数组某一区间同时加上或减去一个定值,只需在差分数组的区间左端和右端后一位各做一次单点修改即可,把区间修改的代价从线性降为常数。

概述

差分数组的价值在于处理大量区间修改后一次性查询的场景。多次区间增减操作全部落到差分数组的端点上累加,待所有修改完成后,对差分数组求前缀和便能还原出更新后的完整原数组。它实现简单、常数极小,是竞赛和工程中处理离线区间修改的首选技巧。

核心原理

• 构造:差分数组第 i 项等于原数组第 i 项减去第 i 减一项,首项即原数组首项。
• 区间修改:对区间左端到右端整体加一个值,只需给差分数组左端加该值、给右端后一位减该值。
• 还原:对差分数组求前缀和即可得到应用全部修改后的原数组,因为前缀和与差分互为逆操作。
• 高维推广:二维差分可用四个角点标记完成矩形区域的整体增减,同样在最后用二维前缀和还原。

应用场景

差分数组常用于航班预订统计、日程重叠计数、给定多个区间的批量加减、图像或矩阵的矩形区域整体调整、以及树上差分求路径覆盖等。凡是先执行大量区间修改、再统一查询最终状态的离线问题,差分数组都能显著降低复杂度。

常见问题

问:差分数组支持修改与查询交替进行吗?答:不擅长。它适合先集中做区间修改再统一还原;若需要修改与查询频繁交替,应改用树状数组或线段树这类支持在线操作的结构。

问:差分和前缀和是什么关系?答:二者互为逆运算,前缀和把差分数组还原为原数组,差分把原数组转回相邻差值,二者配合能高效处理区间修改与区间查询两类问题。