diff[L]   += k
if (R + 1 < n) diff[R+1] -= k

差分数组（Difference Array）及其应用 一、知识点描述 差分数组是一种用于高效处理 区间更新 操作的数据结构。它主要用于解决这样的问题：我们需要对原始数组的某个连续区间中的所有元素，都加上或减去一个相同的常数，并且这样的更新操作会频繁执行多次。在完成所有更新后，我们需要查询最终的数组状态或某个元素的值。 如果使用朴素方法，每次对长度为 L 的区间进行更新（如将所有元素加 k ），时间复杂度为 O(L) 。如果进行 M 次这样的更新，总时间复杂度会达到 O(M * L) ，在处理大规模数据时效率很低。差分数组可以将单次区间更新的时间复杂度优化到 O(1) ，而最终的数组重建（查询）可以在 O(N) 时间内完成（ N 为数组长度）。 二、核心思想与定义 原始数组 ：假设我们有一个长度为 n 的数组 arr[0…n-1] 。 差分数组 ：我们定义一个新的、同样长度为 n 的数组 diff[0…n-1] 。它的定义如下： diff[0] = arr[0] （当 i = 0 时） diff[i] = arr[i] - arr[i-1] （当 1 <= i < n 时） 简单来说， 差分数组的第 i 个元素，等于原始数组第 i 个元素与第 i-1 个元素的差值 。 重要性质 ：从差分数组的定义，我们可以推导出原始数组是差分数组的 前缀和 。 arr[0] = diff[0] arr[1] = diff[0] + diff[1] arr[2] = diff[0] + diff[1] + diff[2] ... 一般地， arr[i] = diff[0] + diff[1] + ... + diff[i] = Σ_{j=0}^{i} diff[j] 三、区间更新的操作原理 这是差分数组最精妙和实用的部分。假设我们需要对原始数组 arr 的区间 [L, R] （包含左右端点）内的所有元素都加上一个值 k 。 朴素方法 ：遍历 i 从 L 到 R ，执行 arr[i] += k 。时间复杂度为 O(R-L+1) 。 差分数组方法 ： 在 diff[L] 上加上 k 。思考一下这个操作的影响：根据 arr[i] 是 diff 前缀和的性质，所有 i >= L 的 arr[i] 在计算前缀和时都会包含这个新加的 k 。也就是说，从位置 L 开始，一直到数组末尾的所有 arr[i] 都隐式地增加了 k 。 在 diff[R+1] 上减去 k （前提是 R+1 < n ）。这个操作是为了“抵消”上一步操作对区间 [R+1, n-1] 产生的影响。因为我们的目标只是更新区间 [L, R] ，所以需要在 R 之后的下一个位置“关闭”这个更新效应。这样，对于所有 i > R 的 arr[i] ，它们的前缀和里就同时包含了 +k 和 -k ，效果抵消，值保持不变。 核心操作总结 ： 要对 arr[L…R] 区间内所有元素加 k ，只需执行： 每次区间更新的时间复杂度是 O(1) 。 四、解题步骤详解 我们通过一个完整的例子来演示如何构建、使用和重建差分数组。 问题 ：初始数组 arr = [1, 3, 5, 2, 4] 。依次执行以下更新操作： 对区间 [1, 3] 所有元素加 2 。 对区间 [0, 2] 所有元素加 -1 （即减1）。 对区间 [2, 4] 所有元素加 3 。 请输出最终数组。 步骤1：构建初始差分数组 diff 根据定义： diff[i] = arr[i] - arr[i-1] (i>0)， diff[0] = arr[0] 。 计算： diff[0] = arr[0] = 1 diff[1] = arr[1] - arr[0] = 3 - 1 = 2 diff[2] = arr[2] - arr[1] = 5 - 3 = 2 diff[3] = arr[3] - arr[2] = 2 - 5 = -3 diff[4] = arr[4] - arr[3] = 4 - 2 = 2 初始差分数组： diff = [1, 2, 2, -3, 2] 步骤2：应用区间更新操作 我们直接在 diff 数组上进行操作。 操作1 ：对 arr[1…3] 加 2 。 L=1 ， R=3 ， k=2 。 diff[1] += 2 → diff[1] 从 2 变为 4 。 R+1=4 ， 4 < n 成立，所以 diff[4] -= 2 → diff[4] 从 2 变为 0 。 更新后 diff = [1, 4, 2, -3, 0] 操作2 ：对 arr[0…2] 加 -1 。 L=0 ， R=2 ， k=-1 。 diff[0] += (-1) → diff[0] 从 1 变为 0 。 R+1=3 ， 3 < n 成立，所以 diff[3] -= (-1) → diff[3] = -3 - (-1) = -2 。（注意是 -= k ，k为-1，所以是 - (-1) 即 +1 ） 更新后 diff = [0, 4, 2, -2, 0] 操作3 ：对 arr[2…4] 加 3 。 L=2 ， R=4 ， k=3 。 diff[2] += 3 → diff[2] 从 2 变为 5 。 R+1=5 ， 5 不小于 n (n=5)，所以不执行 diff[5] 的操作（因为数组越界）。 更新后 diff = [0, 4, 5, -2, 0] 步骤3：从最终差分数组重建原始数组 arr_final 根据性质 arr[i] = Σ_{j=0}^{i} diff[j] ，我们对最终的 diff 数组求前缀和。 arr_final[0] = diff[0] = 0 arr_final[1] = diff[0] + diff[1] = 0 + 4 = 4 arr_final[2] = diff[0] + diff[1] + diff[2] = 0 + 4 + 5 = 9 arr_final[3] = 0 + 4 + 5 + (-2) = 7 arr_final[4] = 0 + 4 + 5 + (-2) + 0 = 7 最终结果数组为： [0, 4, 9, 7, 7] 。 验证 ：我们可以用朴素方法手动计算一下。 初始: [1, 3, 5, 2, 4] 操作1后: [1, 5, 7, 4, 4] 操作2后: [0, 4, 6, 4, 4] 操作3后: [0, 4, 9, 7, 7] 结果一致，验证成功。 五、应用场景与总结 典型应用 ： 频繁的区间加减更新，最后进行单点或全数组查询 。例如，记录航班预订座位、会议室日程安排、像素区域渲染等。 是解决“区间修改、单点查询”或“区间修改、区间查询”（结合前缀和）类问题的高效工具。 许多更复杂的数据结构（如线段树、树状数组的区间更新模式）其思想根源也类似于差分。 时间复杂度分析 ： 构建差分数组 ： O(N) ，一次遍历即可。 单次区间更新 ： O(1) ，只修改两个元素。 重建最终数组（查询） ： O(N) ，计算一次前缀和。 对于 M 次更新，总时间复杂度为 O(N + M) ，远优于朴素的 O(M * L) 。 空间复杂度 ： O(N) ，需要额外存储一个长度为 N 的差分数组。 关键要点 ： 差分是前缀和的逆运算。 区间更新的操作是成对出现的 ( diff[L] += k 和 diff[R+1] -= k )。 差分数组本身通常不直接体现最终值，需要通过 前缀和 还原。 通过掌握差分数组，你就能在常数时间内处理复杂的区间批量更新问题，这是算法竞赛和面试中一个非常实用的技巧。