差分是什么意思

目標(biāo)，掌握差分的概念、和解題的思路

差分就是前綴和的逆過程!!!

一維差分

什么是一維差分?

那么差分可以用來干嘛呢?

讓我們來看這樣一個操作

通過差分,我們可以快速對前綴和數(shù)組的一個區(qū)間的數(shù)進(jìn)去操作

再思考,如何構(gòu)建差分呢??需要構(gòu)建嘛

題目

輸入一個長度為n的整數(shù)序列。

接下來輸入m個操作，每個操作包含三個整數(shù)l, r, c，表示將序列中[l, r]之間的每個數(shù)加上c。

請你輸出進(jìn)行完所有操作后的序列。

題解

這里需要注意:我們構(gòu)造差分的方法是insert(i,i,s[i]);

通過插入的方法我們自然而然的就可以得到差分了

模板

a是s的差分,想要對s[l,r]中的一系列數(shù)操作

a[l] += val;

a[r+1] -= val;

二維差分

和前綴和類似,我們也有二位差分,就是對一個前綴和的矩陣中一系列數(shù)操作

題目

輸入一個n行m列的整數(shù)矩陣，再輸入q個操作，每個操作包含五個整數(shù)x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一個子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。

每個操作都要將選中的子矩陣中的每個元素的值加上c。

請你將進(jìn)行完所有操作后的矩陣輸出。

思路還是一樣,用差分來做

題解

注意:這里輸出的時候用的是BufferWrite()

當(dāng)要輸出大量數(shù)據(jù)的時候可以使用bw,可以有效節(jié)省時間

還有要記得關(guān)閉資源哦!!!

模板

public static void insert(int x1, int y1, int x2, int y2, int val){

a[x1][y1] += val;

a[x1][y2+1] -= val;

a[x2+1][y1] -= val;

a[x2+1][y2+1] += val;

}