Java实现差分数组的示例详解

在本文中，我们将会讲解差分数组的概念以及在Java中使用差分数组的方法。此外，我们还会提供两条使用差分数组的示例方便理解。

差分数组的概念

差分数组是一种特殊的数组，它的元素表示的是原始数组相邻两个元素的差值，例如，原始数组为[1, 3, 5, 7, 9]，那么它对应的差分数组为[2, 2, 2, 2]。

差分数组的优势在于，可以在$O(1)$时间内更新原始数组的某个区间内的元素，这些元素递增或递减同一个值。如果我们需要更新一个区间，例如，需要将原始数组某个区间内的元素都加上$x$，我们只需要将差分数组的左端点对应的元素加上$x$，并将右端点+1对应的元素减去$x$。假设我们需要更新原始数组$A$的区间$[l, r]$，那么可以表示为以下公式：

diff[l] += x
if r+1 < diff.length:
    diff[r+1] -= x

然后我们可以通过遍历差分数组，计算出更新后的原始数组。

使用差分数组的示例

示例1：Leetcode 370. Range Addition

问题描述：给定一个长度为$n$的数组$A$，以及一个形如$[l, r, x]$的三元组，表示将数组$A$中下标从$l$到$r$的元素都加上$x$。请你返回最终的数组。

示例输入：

n = 5
updates = [[1,3,2],[2,4,3],[0,2,-2]]

示例输出：

[0, 2, 3, 5, 3]

解题思路：

这个问题可以使用差分数组来解决，我们先将原始数组初始化为全0，然后遍历三元组的数组$updates$，将差分数组的对应位置加上相应的值。最后再遍历差分数组，计算出更新后的原始数组。

下面是Java代码示例：

public int[] getModifiedArray(int n, int[][] updates) {
    int[] diff = new int[n];
    int[] res = new int[n];
    for (int[] update : updates) {
        diff[update[0]] += update[2];
        if (update[1] + 1 < n)
            diff[update[1] + 1] -= update[2];
    }
    res[0] = diff[0];
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] + diff[i];
    }
    return res;
}

示例2：Leetcode 1109. Corporate Flight Bookings

问题描述：有$n$个航班，它们分别从$0$到$n-1$编号。给定一个长度为$n$的数组$bookings$，其中$bookings[i]=[j, k, num]$表示从航班$j$到航班$k$（包含$k$）的所有航班都需要加上$num$的座位数。请返回更新后的数组。

示例输入：

n = 5
bookings = [[1,2,10],[2,3,20],[2,5,25]]

示例输出：

[0, 10, 55, 45, 25]

解题思路：

我们可以从一个小区间（即一个差分数组的范围）开始考虑这个问题，假如我们需要从第$j$个航班（从零开始编号）到第$i$个航班都加上$x$的座位数，那么我们就需要将差分数组的第$j$个元素加上$x$，将第$i+1$个元素减去$x$，从而到达累加的目的。在最后统计结果的时候，我们只需要对差分数组进行一遍前缀和操作即可，得到更新后的结果。

下面是Java代码示例：

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n+1];
    for (int[] booking : bookings) {
        diff[booking[0]] += booking[2];
        if (booking[1] + 1 <= n)
            diff[booking[1] + 1] -= booking[2];
    }
    int[] res = new int[n];
    res[0] = diff[0];
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] + diff[i];
    }
    return res;
}

总结

差分数组是一种非常实用的工具，在各种算法问题中都有广泛的应用。通过本文提供的两个示例，相信大家可以更加深入地理解和运用差分数组。