小而美的算法能力：差分数组

的前缀和主要适用场景是在不改变原数组的情况下，频繁请求某个区间的累计和。

这里简单介绍一下前缀和。核心代码如下：

class PrefixSum {
    // 前缀和数组
    private int[] prefix;

    /* 输入一个数组，构造前缀和 */
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < prefix.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [i, j] 的累加和 */
    public int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

prefix[i]表示nums[0..i-1]中所有元素的累加和，如果我们要求区间nums[i..j]，我们只需要计算prefix[j+1] - prefix[i]，无需克服整个区间求和。

本文讨论了一种与前缀和思想非常相似的算法技术“差分数组”。 差分数组的主要适用场景往往是在原数组的一定范围内增加或减少元素。

比如我给你设一个数组nums，然后求区间nums[2..6]❀所有nums[3 ..9]全部减3，然后给nums[0..4]全部加2，然后给...

，因为运算猛如虎，然后我问你，最后nums数组的值是多少？

传统的想法非常简单。如果你要求我将 val 添加到间隔 nums [i..j]，我将为所有这些添加一个 for 循环。还能是什么？这个想法的时间复杂度是O(N)。由于这种场景下对nums的修改非常普遍，所以效率会很低。

这里需要用到差分数组的技巧，类似于前缀和技巧构建的前缀数组。我们首先为nums数组构造一个diff差分数组。 diff[i] 是 nums[i] 和 -1nums[ diff 之间的差异 区别 - 数组可以由原始数组nums衍生而来。代码逻辑如下：

int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

这样构造差异数组diff，可以快速进行区间增减操作，如果对区间内所有元素加3 nums[i..j]，那么只要让diff[i] += 3，然后让] -[diff 就够了：

原理是很简单。回忆一下diff数组逆减nums 数组，diff[i] + = 3所有nums[i]相加的过程。 .]，然后 diff[j+1] -= 3，这意味着 。合在一起，是不是意味着3中nums [i..j]中的所有元素都相加了？

只要改变diff数组需要O(1)的时间，就相当于改变了nums的整个区间。多次修改diff，然后通过diff数组进行反转，得到nums的修改结果。

现在我们将差异数组抽象成一个类，包括increment方法和结果♹方法：注意方法中的if语句： 如果j+1 >= diff.length，表示此时不需要给出nums[i]的整个范围，以后也不需要给出。 diff数组减少val。

算法练习

首先关注第370题“区间加法”，直接考察差分数组技巧：

然后我们可以直接实现D类实现这个问题：

int[] getModifiedArray(int length, int[][] updates) {
    // nums 初始化为全 0
    int[] nums = new int[length];
    // 构造差分解法
    Difference df = new Difference(nums);

    for (int[] update : updates) {
        int i = update[0];
        int j = update[1];
        int val = update[2];
        df.increment(i, j, val);
    }

    return df.result();
}

当然，实际的算法问题可能需要我们关联和抽象问题，并且您将无法直接看到我们正在使用差分数组技术。看一下1109题“航班预订”统计”：

函数签名如下：

int[] corpFlightBookings(int[][] bookings, int n)

这道题只是一个迂回题，其实是一道关于差分数组的题，我给你翻译一下：

给出长度为 nnums 的数组，所有元素均为 0。给出另一个 book ，其中包含许多三元组 (i,j, k).每个三元组的含义是要求你nums将数组的闭区间,-1i[ ]中的所有元素与k相加 能否请您返回最新的 nums 数组: PS: n 从 1 开始计数，数组索引从 0 开始，所以对于输入三元组 (i,j, k)数组间隔应对应[i-1,j-1 1个类似问题，利口的第1094题“拼车”。留下简单描述一下问题给我：

你是公交车司机公交车最大载客量是容量，一路上要经过几个车站，我给你一条客运路线int[][]车次，其中

trips[i] = [num, start, end] 代表有 num 名乘客出站 上车结束。请计算一下是否可以同时运送所有乘客（不超过最大载客量容量）。

的函数签名如下：

boolean carPooling(int[][] trips, int capacity);

例如输入：

trips = [[2,1,5],[3,3,7]], capacity = 4

这个不能一次发送，因为travel[1]否则只有2人可以接车会超载变得

相信你已经能想到差分数组技术了：trips[i]表示一组区间运算。乘客上下车相当于数组的区间加减；只要结果数组中的元素都小于capacity，就意味着所有的乘客都可以运输，不会超载。

但问题是，差值数组的长度（站数）应该是多少？题目没有直接指定，但是指定了数据取值范围：

0 <= trips[i][1] < trips[i][2] <= 1000

最大站数是1000，那么我们的差值数组的长度可以直接设置为1001：

boolean carPooling(int[][] trips, int capacity) {
    // 最多有 1000 个车站
    int[] nums = new int[1001];
    // 构造差分解法
    Difference df = new Difference(nums);

    for (int[] trip : trips) {
        // 乘客数量
        int val = trip[0];
        // 第 trip[1] 站乘客上车
        int i = trip[1];
        // 第 trip[2] 站乘客已经下车，
        // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
        int j = trip[2] - 1;
        // 进行区间操作
        df.increment(i, j, val);
    }

    int[] res = df.result();

    // 客车自始至终都不应该超载
    for (int i = 0; i < res.length; i++) {
        if (capacity < res[i]) {
            return false;
        }
    }
    return true;
}

此时，这道题就是解决了。

最后，差分数组和前缀和数组是相对常见且巧妙的算法技术。它们适用于各种常见情况，对于懂的人来说不难，但是对于难的人来说就不难了。那么，你学会使用差分数组了吗？