差分数组是一种与前缀和思想相似的算法技巧，主要用于频繁对原始数组的某个区间元素进行增减操作的场景。

核心应用场景

当需要多次对数组的特定区间进行加减操作时，常规的思路很容易，你让我给区间 nums[i..j] 加上 val，那我就一个 for 循环给它们都加上呗，还能咋样？这种思路的时间复杂度是 O(N)O(N)，由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。

这里就需要差分数组的技巧，类似前缀和技巧构造的 preSum 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：使用差分数组可以大大提高效率。

差分数组通过记录相邻元素的差值来构建，这样对原数组某个区间的批量操作，在差分数组中只需要修改两个位置的值即可完成。

1
2
3
4
5
int diff[nums.size()]; // 构造差分数组 
diff[0] = nums[0]; 
for (int i = 1; i < nums.size(); i++) { 
	diff[i] = nums[i] - nums[i - 1]; 
	}

通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

1
2
3
4
5
6
int res[diff.size()];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.size(); i++) {
    res[i] = res[i - 1] + diff[i];
}

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：
原理很简单，回想 diff 数组反推 nums 数组的过程，diff[i] += 3 意味着给 nums[i..] 所有的元素都加了 3，然后 diff[j+1] -= 3 又意味着对于 nums[j+1..] 所有元素再减 3，那综合起来，是不是就是对 nums[i..j] 中的所有元素都加 3 了？

只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。多次修改 diff，然后通过 diff 数组反推，即可得到 nums 修改后的结果。

优势

相比直接遍历区间进行修改，差分数组的时间复杂度从 O(n)O(n) 降低到 O(1)O(1)，特别适合需要大量区间修改操作的场景。

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 差分数组工具类
class Difference {
    // 差分数组
    private:
        vector<int> diff;
    
    // 输入一个初始数组，区间操作将在这个数组上进行
    public:
        Difference(vector<int>& nums) {
            diff = vector<int>(nums.size());
            // 根据初始数组构造差分数组
            diff[0] = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        // 给闭区间 [i, j] 增加 val（可以是负数）
        void increment(int i, int j, int val) {
            diff[i] += val;
            if (j + 1 < diff.size()) {
                diff[j + 1] -= val;
            }
        }

        // 返回结果数组
        vector<int> result() {
            vector<int> res(diff.size());
            // 根据差分数组构造结果数组
            res[0] = diff[0];
            for (int i = 1; i < diff.size(); i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
};

当 j+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了。

例题

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：

输入：bookings = 1,2,10],[2,3,20],[2,5,25, n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

提示：

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

题目来源：力扣 1109. 航班预订统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {

public:

    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

        vector<int> nums(n,0);

        Difference df(nums);

        for(const auto& booking:bookings){

            int i = booking[0] -1;

            int j = booking[1] -1;

            int val = booking[2];

            df.increment(i,j,val);

        }
        return df.result();
    }

private:

    class Difference {

        // 差分数组

        vector<int> diff;


    public:

        Difference(const vector<int>& nums) {

            assert(!nums.empty());

            diff.resize(nums.size());

            // 构造差分数组

            diff[0] = nums[0];

            for (size_t i = 1; i < nums.size(); ++i) {

                diff[i] = nums[i] - nums[i - 1];

            }

        }

  

        // 给闭区间 [i, j] 增加 val（可以是负数）

        void increment(int i, int j, int val) {

            diff[i] += val;

            if (j + 1 < diff.size()) {

                diff[j + 1] -= val;

            }

        }

  

        vector<int> result() {

            vector<int> res(diff.size());

            // 根据差分数组构造结果数组

            res[0] = diff[0];

            for (size_t i = 1; i < diff.size(); ++i) {

                res[i] = res[i - 1] + diff[i];

            }

            return res;

        }

    };

};

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

**输入：**trips = [[2,1,5],[3,3,7]], capacity = 4
**输出：**false

示例 2：

**输入：**trips = [[2,1,5],[3,3,7]], capacity = 5
**输出：**true

提示：

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengersi <= 100
  • 0 <= fromi < toi <= 1000
  • 1 <= capacity <= 105

题目来源：力扣 1094. 拼车。

联想到差分数组技巧：trips[i] 代表着一组区间操作，旅客的上车和下车就相当于数组的区间加减；只要结果数组中的元素都小于 capacity，就说明可以不超载运输所有旅客。

车站编号从 0 开始，最多到 1000，也就是最多有 1001 个车站，那么我们的差分数组长度可以直接设置为 1001，这样索引刚好能够涵盖所有车站的编号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 最多有 1000 个车站
        vector<int> nums(1001, 0);
        // 构造差分解法
        Difference df(nums);

        for (const auto& 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);
        }

        vector<int> res = df.result();

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

    // 差分数组工具类
    class Difference {
    private:
        // 差分数组
        vector<int> diff;

    public:
        // 输入一个初始数组，区间操作将在这个数组上进行
        Difference(vector<int>& nums) {
            assert(!nums.empty());
            diff.resize(nums.size());
            // 根据初始数组构造差分数组
            diff[0] = nums[0];
            for (int i = 1; i < nums.size(); i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        // 给闭区间 [i, j] 增加 val（可以是负数）
        void increment(int i, int j, int val) {
            diff[i] += val;
            if (j + 1 < diff.size()) {
                diff[j + 1] -= val;
            }
        }

        // 返回结果数组
        vector<int> result() {
            vector<int> res(diff.size());
            // 根据差分数组构造结果数组
            res[0] = diff[0];
            for (int i = 1; i < diff.size(); i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
    };
};

思考

  • 第一个问题，想要使用差分数组技巧，必须创建一个长度和区间长度一样的差分数组 diff，那如果我有一个非常大的区间，比如 [0, 10^9]，那岂不是上来就要创建一个长度为 10^9 的数组，才能开始区间增减操作？

  • 第二个问题，前缀和技巧可以快速进行区间查询，差分数组可以快速进行区间增减。能不能把他俩结合起来，既可以快速进行区间增减，又可以随时进行区间查询？

其实这两个问题是处理区间问题的常见问题，终极答案是 线段树 这种数据结构，它可以在 O(logN)O(logN) 的时间复杂度内完成任意长度的区间增减和区间查询操作。