讀完本文咐容，你可以去力扣拿下如下題目：
-----------
前文 前綴和技巧詳解 寫過的前綴和技巧是非常常用的算法技巧悠砚，前綴和主要適用的場景是原始數(shù)組不會(huì)被修改的情況下凹嘲，頻繁查詢某個(gè)區(qū)間的累加和呜魄。
沒看過前文沒關(guān)系悔叽，這里簡單介紹一下前綴和，核心代碼就是下面這段：
class PrefixSum {
// 前綴和數(shù)組
private int[] prefix;
/* 輸入一個(gè)數(shù)組爵嗅，構(gòu)造前綴和 */
public PrefixSum(int[] nums) {
prefix = new int[nums.length + 1];
// 計(jì)算 nums 的累加和
for (int i = 1; i < prefix.length; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
}
/* 查詢閉區(qū)間 [i, j] 的累加和 */
public int query(int i, int j) {
return prefix[j + 1] - prefix[i];
}
}
prefix[i] 就代表著 nums[0..i-1] 所有元素的累加和娇澎，如果我們想求區(qū)間 nums[i..j] 的累加和，只要計(jì)算 prefix[j+1] - prefix[i] 即可睹晒，而不需要遍歷整個(gè)區(qū)間求和趟庄。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目伪很，全部發(fā)布在 labuladong的算法小抄戚啥，持續(xù)更新。建議收藏是掰，按照我的文章順序刷題虑鼎，掌握各種算法套路后投再入題海就如魚得水了。
本文講一個(gè)和前綴和思想非常類似的算法技巧「差分?jǐn)?shù)組」键痛，差分?jǐn)?shù)組的主要適用場景是頻繁對原始數(shù)組的某個(gè)區(qū)間的元素進(jìn)行增減炫彩。
比如說，我給你輸入一個(gè)數(shù)組 nums絮短，然后又要求給區(qū)間 nums[2..6] 全部加 1江兢，再給 nums[3..9] 全部減 3，再給 nums[0..4] 全部加 2丁频，再給...
一通操作猛如虎杉允，然后問你，最后 nums 數(shù)組的值是什么席里？
常規(guī)的思路很容易叔磷，你讓我給區(qū)間 nums[i..j] 加上 val，那我就一個(gè) for 循環(huán)給它們都加上唄奖磁，還能咋樣改基？這種思路的時(shí)間復(fù)雜度是 O(N)，由于這個(gè)場景下對 nums 的修改非常頻繁咖为，所以效率會(huì)很低下秕狰。
這里就需要差分?jǐn)?shù)組的技巧，類似前綴和技巧構(gòu)造的 prefix 數(shù)組躁染，我們先對 nums 數(shù)組構(gòu)造一個(gè) diff 差分?jǐn)?shù)組鸣哀，diff[i] 就是 nums[i] 和 nums[i-1] 之差：
int[] diff = new int[nums.length];
// 構(gòu)造差分?jǐn)?shù)組
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
通過這個(gè) diff 差分?jǐn)?shù)組是可以反推出原始數(shù)組 nums 的，代碼邏輯如下：
int[] res = new int[diff.length];
// 根據(jù)差分?jǐn)?shù)組構(gòu)造結(jié)果數(shù)組
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
這樣構(gòu)造差分?jǐn)?shù)組 diff吞彤，就可以快速進(jìn)行區(qū)間增減的操作我衬，如果你想對區(qū)間 nums[i..j] 的元素全部加 3，那么只需要讓 diff[i] += 3，然后再讓 diff[j+1] -= 3 即可：
原理很簡單低飒，回想 diff 數(shù)組反推 nums 數(shù)組的過程许昨，diff[i] += 3 意味著給 nums[i..] 所有的元素都加了 3懂盐，然后 diff[j+1] -= 3 又意味著對于 nums[j+1..] 所有元素再減 3褥赊，那綜合起來，是不是就是對 nums[i..j] 中的所有元素都加 3 了莉恼？
只要花費(fèi) O(1) 的時(shí)間修改 diff 數(shù)組拌喉，就相當(dāng)于給 nums 的整個(gè)區(qū)間做了修改。多次修改 diff俐银，然后通過 diff 數(shù)組反推尿背，即可得到 nums 修改后的結(jié)果。
現(xiàn)在我們把差分?jǐn)?shù)組抽象成一個(gè)類捶惜，包含 increment 方法和 result 方法：
class Difference {
// 差分?jǐn)?shù)組
private int[] diff;
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 構(gòu)造差分?jǐn)?shù)組
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 給閉區(qū)間 [i,j] 增加 val（可以是負(fù)數(shù)）*/
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];
// 根據(jù)差分?jǐn)?shù)組構(gòu)造結(jié)果數(shù)組
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;
}
}
當(dāng) j+1 >= diff.length 時(shí)田藐，說明是對 nums[i] 及以后的整個(gè)數(shù)組都進(jìn)行修改，那么就不需要再給 diff 數(shù)組減 val 了吱七。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)汽久，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄踊餐，持續(xù)更新景醇。建議收藏，按照我的文章順序刷題吝岭，掌握各種算法套路后投再入題海就如魚得水了三痰。
算法實(shí)踐
這里看一下力扣第 1109 題「航班預(yù)訂統(tǒng)計(jì)」：
函數(shù)簽名如下：
int[] corpFlightBookings(int[][] bookings, int n)
這個(gè)題目就在那繞彎彎，其實(shí)它就是個(gè)差分?jǐn)?shù)組的題窜管，我給你翻譯一下：
給你輸入一個(gè)長度為 n 的數(shù)組 nums散劫，其中所有元素都是 0。再給你輸入一個(gè) bookings幕帆，里面是若干三元組 (i,j,k)获搏，每個(gè)三元組的含義就是要求你給 nums 數(shù)組的閉區(qū)間 [i-1,j-1] 中所有元素都加上 k。請你返回最后的 nums 數(shù)組是多少蜓肆？
PS：因?yàn)轭}目說的 n 是從 1 開始計(jì)數(shù)的颜凯，而數(shù)組索引從 0 開始，所以對于輸入的三元組 (i,j,k)仗扬，數(shù)組區(qū)間應(yīng)該對應(yīng) [i-1,j-1]症概。
這么一看，不就是一道標(biāo)準(zhǔn)的差分?jǐn)?shù)組題嘛早芭？我們可以直接復(fù)用剛才寫的類：
int[] corpFlightBookings(int[][] bookings, int n) {
// nums 初始化為全 0
int[] nums = new int[n];
// 構(gòu)造差分解法
Difference df = new Difference(nums);
for (int[] booking : bookings) {
// 注意轉(zhuǎn)成數(shù)組索引要減一哦
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
// 對區(qū)間 nums[i..j] 增加 val
df.increment(i, j, val);
}
// 返回最終的結(jié)果數(shù)組
return df.result();
}
這道題就解決了彼城。
其實(shí)我覺得差分?jǐn)?shù)組和前綴和數(shù)組都是比較常見且巧妙的算法技巧，分別適用不同的常見，而且是會(huì)者不難募壕，難者不會(huì)调炬。所以，關(guān)于差分?jǐn)?shù)組的使用舱馅，你學(xué)會(huì)了嗎缰泡？
學(xué)會(huì)的話，分享/點(diǎn)贊/在看三連走起代嗤？
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章棘钞，手把手帶刷 200 道力扣題目，建議收藏干毅！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star宜猜，歡迎標(biāo)星！
