一維差分?jǐn)?shù)組

假設(shè)給你一個(gè)數(shù)組 nums ，先對(duì)區(qū)間 [a,b] 中每個(gè)元素加 3 ，在對(duì)區(qū)間 [c,d] 每個(gè)元素減 5 ?…… ?，這樣非常頻繁的區(qū)間修改，常規(guī)的做法可以一個(gè)個(gè)計(jì)算。

頻繁對(duì)數(shù)組的一段區(qū)間進(jìn)行增加或減去同一個(gè)值，如果一個(gè)個(gè)去操作，很明顯效率很差，我們可以使用差分?jǐn)?shù)組，差分?jǐn)?shù)組就是原始數(shù)組相鄰元素之間的差。定義差分?jǐn)?shù)組 d[n] ，我們可以得到： d[i] = nums[i] ? nums[i?1] ，其中 d[0] = nums[0] ，如下圖所示。

我們可以看到原數(shù)組就是差分?jǐn)?shù)組的前綴和。

有了差分?jǐn)?shù)組，如果對(duì)區(qū)間 [a,b] 每個(gè)元素加 3 ，不需要在一個(gè)個(gè)操作，只需要在兩端修改即可，如下圖所示。

來(lái)看下代碼：

二維差分?jǐn)?shù)組

我們把一維差分?jǐn)?shù)組看做是一條直線，只需要用后面的值減去前面的值就可以構(gòu)造差分?jǐn)?shù)組。而二維差分?jǐn)?shù)可以把他看做是一個(gè)平面，如下圖所示，他的定義如下：

如果想獲取原數(shù)組，根據(jù)上面的公式可以得到：

如下圖所示，以 (x1,y1) 為左上角， (x2,y2) 為右下角構(gòu)成一個(gè)區(qū)間，如果對(duì)這個(gè)區(qū)間內(nèi)的每個(gè)元素增加 val ，只需要執(zhí)行下面四步即可。

代碼如下：

?