讀完本文，你可以去力扣拿下如下題目：

1109.航班預訂統計

-----------

前文 字首和技巧詳解 寫過的字首和技巧是非常常用的演算法技巧，字首和主要適用的場景是原始陣列不會被修改的情況下，頻繁查詢某個區間的累加和。

沒看過前文沒關係，這裡簡單介紹一下字首和，核心程式碼就是下面這段：

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] 全部加 1，再給 nums[3..9] 全部減 3，再給 nums[0..4] 全部加 2，再給...

一通操作猛如虎，然後問你，最後 nums 陣列的值是什麼？

常規的思路很容易，你讓我給區間 nums[i..j] 加上 val，那我就一個 for 迴圈給它們都加上唄，還能咋樣？這種思路的時間複雜度是 O(N)，由於這個場景下對 nums 的修改非常頻繁，所以效率會很低下。

這裡就需要差分陣列的技巧，類似字首和技巧構造的 prefix 陣列，我們先對 nums 陣列構造一個 diff 差分陣列，diff[i] 就是 nums[i] 和 nums[i-1] 之差：

int[] diff = new int[nums.length];// 構造差分陣列diff[0] = nums[0];for (int i = 1; i < nums.length; i++) {    diff[i] = nums[i] - nums[i - 1];}

透過這個 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，就可以快速進行區間增減的操作，如果你想對區間 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 修改後的結果。

現在我們把差分陣列抽象成一個類，包含 increment 方法和 result 方法：

class Difference {    // 差分陣列    private int[] diff;    public Difference(int[] nums) {        assert nums.length > 0;        diff = new int[nums.length];        // 構造差分陣列        diff[0] = nums[0];        for (int i = 1; i < nums.length; i++) {            diff[i] = nums[i] - nums[i - 1];        }    }    /* 給閉區間 [i,j] 增加 val（可以是負數）*/    public void increment(int i, int j, int val) {        diff[i] += val;        if (j + 1 < diff.length) {            diff[j + 1] -= val;        }    }​    public int[] result() {        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];        }        return res;    }}

這裡注意一下 increment 方法中的 if 語句：

public void increment(int i, int j, int val) {    diff[i] += val;    if (j + 1 < diff.length) {        diff[j + 1] -= val;    }}

當 j+1 >= diff.length 時，說明是對 nums[i] 及以後的整個陣列都進行修改，那麼就不需要再給 diff 陣列減 val 了。

演算法實踐

這裡看一下力扣第 1109 題「航班預訂統計」：

函式簽名如下：

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

這個題目就在那繞彎彎，其實它就是個差分陣列的題，我給你翻譯一下：

給你輸入一個長度為 n 的陣列 nums，其中所有元素都是 0。再給你輸入一個 bookings，裡面是若干三元組 (i,j,k)，每個三元組的含義就是要求你給 nums 陣列的閉區間 [i-1,j-1] 中所有元素都加上 k。請你返回最後的 nums 陣列是多少？

PS：因為題目說的 n 是從 1 開始計數的，而陣列索引從 0 開始，所以對於輸入的三元組 (i,j,k)，陣列區間應該對應 [i-1,j-1]。

這麼一看，不就是一道標準的差分陣列題嘛？我們可以直接複用剛才寫的類：

int[] corpFlightBookings(int[][] bookings, int n) {    // nums 初始化為全 0    int[] nums = new int[n];    // 構造差分解法    Difference df = new Difference(nums);​    for (int[] booking : bookings) {        // 注意轉成陣列索引要減一哦        int i = booking[0] - 1;        int j = booking[1] - 1;        int val = booking[2];        // 對區間 nums[i..j] 增加 val        df.increment(i, j, val);    }    // 返回最終的結果陣列    return df.result();}

這道題就解決了。

其實我覺得差分陣列和字首和陣列都是比較常見且巧妙的演算法技巧，分別適用不同的常見，而且是會者不難，難者不會。所以，關於差分陣列的使用，你學會了嗎？