1. 從“一維”到“二維”差分思想的升維思考在算法和數(shù)據(jù)結(jié)構(gòu)的領(lǐng)域里差分是一個(gè)極其高效且優(yōu)雅的工具它把區(qū)間修改的時(shí)間復(fù)雜度從 O(n) 降到了 O(1)。很多朋友對(duì)一維差分已經(jīng)駕輕就熟給定一個(gè)原數(shù)組a我們構(gòu)造一個(gè)差分?jǐn)?shù)組d使得d[i] a[i] - a[i-1]邊界特殊處理。這樣一來如果我們想對(duì)原數(shù)組a的區(qū)間[l, r]統(tǒng)一加上一個(gè)值c只需要在差分?jǐn)?shù)組d上執(zhí)行d[l] c和d[r1] - c即可。修改完成后對(duì)差分?jǐn)?shù)組d求一次前綴和就能得到修改后的a數(shù)組。這個(gè)“修改O(1)查詢O(n)”的套路在處理大量區(qū)間更新、單點(diǎn)查詢或最終統(tǒng)一查詢的場景下比如批量增減、日程安排沖突檢測等威力巨大。那么當(dāng)問題從一條線擴(kuò)展到一個(gè)平面時(shí)我們?cè)撛趺崔k想象一下這樣的場景你有一個(gè)數(shù)字圖像一個(gè)二維矩陣需要對(duì)其中任意一個(gè)矩形區(qū)域內(nèi)的所有像素值進(jìn)行統(tǒng)一的亮度調(diào)整比如增加某個(gè)值或者在一個(gè)模擬城市建設(shè)的網(wǎng)格地圖上你規(guī)劃了一片矩形區(qū)域要新建住宅需要給該區(qū)域內(nèi)所有地塊的人口容量增加一個(gè)固定值。如果暴力遍歷矩形內(nèi)的每一個(gè)格子進(jìn)行修改假設(shè)矩形大小為m*n每次修改就是 O(m*n) 的復(fù)雜度。如果這種修改操作非常頻繁程序性能很快就會(huì)成為瓶頸。二維差分就是一維差分思想在二維空間上的自然延伸。它的核心目標(biāo)同樣沒變將對(duì)一個(gè)子矩陣矩形區(qū)域內(nèi)所有元素的批量修改操作轉(zhuǎn)化為對(duì)差分矩陣上僅僅四個(gè)頂點(diǎn)的O(1)常數(shù)時(shí)間修改。理解并掌握二維差分意味著你解鎖了處理網(wǎng)格類、圖像類、地圖類問題中區(qū)間區(qū)域更新問題的“王牌技能”。很多算法競賽題目和實(shí)際工程問題如圖像處理中的ROI操作、游戲中的區(qū)域效果、數(shù)據(jù)統(tǒng)計(jì)中的區(qū)塊累計(jì)都會(huì)直接或間接用到它。我最初學(xué)習(xí)時(shí)曾試圖死記硬背那個(gè)“四個(gè)點(diǎn)加減”的公式但很快就混淆了。后來我發(fā)現(xiàn)必須從一維的原理出發(fā)自己推導(dǎo)一遍二維的公式才能真正內(nèi)化并且在遇到三維甚至更高維差分時(shí)也能觸類旁通。接下來我們就扔掉死記硬背從最本質(zhì)的“前綴和”與“差分”的互逆關(guān)系出發(fā)一步步構(gòu)建出二維差分的完整操作邏輯。2. 二維前綴和與差分的定義與互逆關(guān)系要理解二維差分必須先徹底理解它的“另一半”——二維前綴和。它們是互逆的運(yùn)算就像加法和減法、積分和微分一樣。假設(shè)我們有一個(gè)原始二維矩陣a其行、列下標(biāo)均從1開始從1開始能避免很多邊界判斷的麻煩推薦在算法實(shí)現(xiàn)中采用。我們定義二維前綴和矩陣s其中s[i][j]表示原始矩陣a中從左上角(1, 1)到右下角(i, j)所圍成的矩形區(qū)域內(nèi)所有元素的和。用公式表示就是s[i][j] a[1][1] a[1][2] ... a[i][j]即所有xi, yj的a[x][y]之和那么如何快速計(jì)算s[i][j]呢這里有一個(gè)經(jīng)典的遞推公式容斥原理s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]這個(gè)公式怎么來的s[i-1][j]是(1,1)到(i-1, j)的和它覆蓋了黃色和綠色區(qū)域。s[i][j-1]是(1,1)到(i, j-1)的和覆蓋了黃色和藍(lán)色區(qū)域。這兩個(gè)加起來黃色區(qū)域被加了兩次綠色和藍(lán)色區(qū)域各加了一次而我們需要的s[i][j]是黃、綠、藍(lán)、紅四個(gè)區(qū)域的總和。多減了一次的黃色區(qū)域正好是s[i-1][j-1]最后再加上當(dāng)前格子a[i][j]紅色區(qū)域就得到了正確的結(jié)果。這個(gè)計(jì)算過程是 O(1) 的我們可以用雙重循環(huán)在 O(n*m) 時(shí)間內(nèi)預(yù)處理出整個(gè)前綴和矩陣s。有了前綴和我們可以在 O(1) 時(shí)間內(nèi)計(jì)算任意子矩陣(x1, y1)到(x2, y2)的和sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]原理同樣是容斥大矩形減去左邊和上邊的兩個(gè)矩形再把多減了一次的左上角小矩形加回來?，F(xiàn)在主角差分登場了。我們定義二維差分矩陣d它和原始矩陣a滿足這樣的關(guān)系原始矩陣a是差分矩陣d的二維前綴和。換句話說對(duì)差分矩陣d求二維前綴和就能得到原始矩陣a。即a[i][j] 從 (1,1) 到 (i,j) 對(duì) d 矩陣求和的結(jié)果 用公式表達(dá)就是a[i][j] Σ_{x1}^{i} Σ_{y1}^{j} d[x][y]。反過來如何根據(jù)原始矩陣a構(gòu)造它的差分矩陣d呢我們可以利用它們和前綴和s的關(guān)系來思考。實(shí)際上a可以直接看作它自身的“值矩陣”。構(gòu)造d的一種直觀方法是把每個(gè)a[i][j]看作是對(duì)一個(gè)以(i, j)為左上角(i, j)為右下角的“單點(diǎn)矩陣”進(jìn)行的修改操作。那么差分矩陣d的初始化可以全為0。然后對(duì)于每個(gè)位置(i, j)我們執(zhí)行一次“對(duì)以(i,j)為左上角和右下角的1x1矩陣增加a[i][j]”的操作。這個(gè)操作作用于差分矩陣d上就是后續(xù)要講的四個(gè)點(diǎn)的修改。通過遍歷所有(i, j)并執(zhí)行這個(gè)操作最終得到的d矩陣就是a對(duì)應(yīng)的差分矩陣。更常用且簡單的初始化方法是利用前綴和遞推公式的逆運(yùn)算。回憶前綴和公式s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]。如果我們把s看作a把a(bǔ)看作d因?yàn)閍是d的前綴和那么可以得到a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1] d[i][j]移項(xiàng)后就得到了差分矩陣d的構(gòu)造公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]這個(gè)公式可以讓我們?cè)?O(n*m) 時(shí)間內(nèi)由原始矩陣a構(gòu)造出差分矩陣d。注意這個(gè)公式是理解后續(xù)區(qū)域修改操作的關(guān)鍵基礎(chǔ)。3. 二維差分矩陣的核心操作區(qū)域修改與單點(diǎn)查詢現(xiàn)在進(jìn)入最精彩的部分如何利用差分矩陣d實(shí)現(xiàn)對(duì)一個(gè)矩形區(qū)域的快速修改。假設(shè)我們要對(duì)原矩陣a中以(x1, y1)為左上角(x2, y2)為右下角的矩形區(qū)域內(nèi)的每一個(gè)元素都加上一個(gè)常數(shù)c。在差分的思想下我們不對(duì)原矩陣a進(jìn)行遍歷修改而是只修改差分矩陣d上的四個(gè)點(diǎn)。操作如下d[x1][y1] cd[x1][y21] - cd[x21][y1] - cd[x21][y21] c為什么修改這四個(gè)點(diǎn)就能達(dá)到效果我們可以從一維差分類比過來也可以從二維前綴和的定義進(jìn)行推導(dǎo)。從一維類比理解把二維問題先降維成一維。固定某一行i對(duì)列區(qū)間[y1, y2]的修改在一維差分里是d[i][y1] c和d[i][y21] - c?，F(xiàn)在我們的矩形是從第x1行到第x2行所以我們需要對(duì)所有i在[x1, x2]范圍內(nèi)的行都執(zhí)行這個(gè)一維操作。這等價(jià)于在d[x1][y1]處c表示從x1行開始所有行的y1列差分都c。在d[x21][y1]處-c表示從x21行開始取消掉剛才對(duì)y1列的影響。同理對(duì)于y21列這個(gè)“終止邊界”我們需要在x1行-c在x21行c來抵消。組合起來就是上面四個(gè)操作。從二維前綴和公式嚴(yán)格推導(dǎo)推薦掌握記住a是d的二維前綴和。修改后我們希望對(duì)于矩形內(nèi)的點(diǎn)(i, j)即x1ix2, y1jy2其新的a[i][j]等于舊的a[i][j] c對(duì)于矩形外的點(diǎn)a[i][j]保持不變。 考慮修改后的差分矩陣d和原差分矩陣d的關(guān)系。設(shè)變化量delta_d就是我們上面操作的四個(gè)點(diǎn)。 那么對(duì)于任意點(diǎn)(i, j)修改后的值a[i][j] 對(duì) d 求前綴和 對(duì) (d delta_d) 求前綴和 a[i][j] (對(duì) delta_d 求前綴和)。 現(xiàn)在我們只需要讓“對(duì)delta_d求前綴和”這個(gè)結(jié)果在(i, j)位于矩形內(nèi)時(shí)為c在矩形外時(shí)為0。觀察delta_d的四個(gè)操作在(x1, y1)處c這意味著所有以(x1, y1)為矩形右下角或包含該點(diǎn)的前綴和計(jì)算都會(huì)多一個(gè)c。也就是所有ix1, jy1的點(diǎn)其前綴和都會(huì)c。在(x1, y21)處-c這會(huì)抵消掉對(duì)于jy21的列的影響。使得對(duì)于ix1, jy21的區(qū)域凈變化為c (-c) 0。在(x21, y1)處-c這會(huì)抵消掉對(duì)于ix21的行的影響。使得對(duì)于ix21, jy1的區(qū)域凈變化為c (-c) 0。在(x21, y21)處c由于上面兩個(gè)-c在(ix21, jy21)的區(qū)域多減了一個(gè)c因?yàn)樵搮^(qū)域同時(shí)滿足兩個(gè)抵消條件所以需要c補(bǔ)回來使得該區(qū)域凈變化為0。最終的效果就是只有同時(shí)滿足ix1, jy1且ix2, jy2的點(diǎn)即我們的目標(biāo)矩形區(qū)域其前綴和變化量才是c。其他區(qū)域通過正負(fù)抵消變化量均為0。完美達(dá)成了目標(biāo)。注意這里有一個(gè)非常關(guān)鍵的細(xì)節(jié)就是下標(biāo)的邊界。y21和x21可能會(huì)超出矩陣的實(shí)際范圍。在實(shí)現(xiàn)時(shí)我們通常會(huì)把差分?jǐn)?shù)組d的大小聲明得比原矩陣a多一行一列例如a是n*md聲明為(n2)*(m2)下標(biāo)從1開始使用。這樣x21和y21即使等于n1或m1也仍在數(shù)組有效范圍內(nèi)無需特殊判斷。這是一個(gè)非常重要的編程技巧能極大簡化代碼邏輯。修改完成后如果我們想得到修改后的原矩陣a只需要對(duì)差分矩陣d求一次二維前綴和即可。求前綴和的公式就是前面提到的a[i][j] d[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]我們可以直接用這個(gè)遞推公式用d覆蓋或計(jì)算出新的a矩陣。4. 從理論到實(shí)戰(zhàn)典型問題分析與代碼實(shí)現(xiàn)理解了原理我們來看幾個(gè)典型問題并給出清晰的代碼實(shí)現(xiàn)模板。我將使用C語言描述但其邏輯可以輕松移植到Java、Python等任何語言。4.1 問題一靜態(tài)初始化與區(qū)域修改這是最基礎(chǔ)的場景。我們已知一個(gè)原始的n * m矩陣a然后有一系列操作每個(gè)操作指定一個(gè)矩形區(qū)域(x1, y1, x2, y2)和一個(gè)值c表示給該矩形區(qū)域內(nèi)所有數(shù)加c。所有操作完成后輸出最終矩陣。解題步驟根據(jù)原始矩陣a構(gòu)造其差分矩陣d。使用公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。為了方便我們可以假設(shè)初始a是全0矩陣然后認(rèn)為初始矩陣就是通過一系列“對(duì)1x1矩陣的添加操作”得到的。更簡單的初始化方法是直接創(chuàng)建一個(gè)全0的(n2)*(m2)大小的差分?jǐn)?shù)組d然后遍歷a對(duì)每個(gè)(i, j)執(zhí)行add(i, j, i, j, a[i][j])操作。這個(gè)add函數(shù)就是上面提到的四步操作函數(shù)。對(duì)于每一個(gè)區(qū)域增加操作(x1, y1, x2, y2, c)調(diào)用add(x1, y1, x2, y2, c)更新差分?jǐn)?shù)組d。所有操作完成后對(duì)差分?jǐn)?shù)組d執(zhí)行二維前綴和計(jì)算得到的結(jié)果就是最終矩陣。C代碼模板#include iostream #include vector using namespace std; // 二維差分模板 // n, m 為原矩陣大小 // diff 為 (n2) x (m2) 的差分矩陣下標(biāo)從1開始 void add(vectorvectorint diff, int x1, int y1, int x2, int y2, int c) { diff[x1][y1] c; diff[x1][y21] - c; diff[x21][y1] - c; diff[x21][y21] c; } int main() { int n, m, q; // 矩陣行數(shù)列數(shù)操作次數(shù) cin n m q; vectorvectorint a(n1, vectorint(m1)); vectorvectorint diff(n2, vectorint(m2, 0)); // 差分?jǐn)?shù)組多開空間 // 1. 讀入原始矩陣并構(gòu)建差分?jǐn)?shù)組 // 方法將每個(gè)a[i][j]視為對(duì)(i,j)到(i,j)這個(gè)單點(diǎn)矩陣的添加操作 for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; add(diff, i, j, i, j, a[i][j]); // 初始化差分 } } // 2. 執(zhí)行q次區(qū)域修改操作 while (q--) { int x1, y1, x2, y2, c; cin x1 y1 x2 y2 c; add(diff, x1, y1, x2, y2, c); } // 3. 對(duì)差分?jǐn)?shù)組求前綴和得到最終矩陣 vectorvectorint ans(n1, vectorint(m1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { // 前綴和遞推公式 ans[i][j] diff[i][j] ans[i-1][j] ans[i][j-1] - ans[i-1][j-1]; cout ans[i][j] ; } cout endl; } return 0; }4.2 問題二動(dòng)態(tài)初始化與多次查詢另一種常見場景是初始矩陣全為0。然后有一系列區(qū)域增加操作。操作過程中或操作結(jié)束后可能會(huì)有查詢查詢某個(gè)位置(i, j)的值或者查詢某個(gè)子矩陣的和。對(duì)于單點(diǎn)查詢?cè)诿看螀^(qū)域修改后我們只需要對(duì)差分矩陣d求前綴和到那個(gè)點(diǎn)即可。但如果查詢很頻繁我們可以在所有修改操作完成后一次性計(jì)算出整個(gè)前綴和矩陣即最終矩陣然后每次查詢就是 O(1) 的。對(duì)于子矩陣和查詢我們需要的是最終矩陣的二維前綴和矩陣s。流程是所有修改操作作用于差分?jǐn)?shù)組d- 對(duì)d求前綴和得到最終矩陣a- 對(duì)a求二維前綴和得到s矩陣。之后任何子矩陣和查詢都可以用s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]這個(gè)公式在 O(1) 時(shí)間內(nèi)回答。這里有一個(gè)重要的優(yōu)化技巧我們可以將“求差分?jǐn)?shù)組d的前綴和得到a”和“求a的前綴和得到s”兩個(gè)步驟合并。實(shí)際上s[i][j]可以直接從d計(jì)算出來公式為s[i][j] d[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]然后s[i][j]再參與下一輪s[i1][j]等的計(jì)算。也就是說我們可以把d直接當(dāng)成“差分的前綴和”的增量來計(jì)算最終的前綴和矩陣s。在代碼實(shí)現(xiàn)上就是用一個(gè)數(shù)組同時(shí)完成累積。4.3 實(shí)戰(zhàn)中的“踩坑點(diǎn)”與經(jīng)驗(yàn)總結(jié)在實(shí)際編碼和解題中有幾個(gè)坑點(diǎn)需要特別注意下標(biāo)從1開始這是最重要的習(xí)慣。將矩陣有效數(shù)據(jù)存儲(chǔ)在索引1~n和1~m并為此多分配數(shù)組空間如n2,m2。這能統(tǒng)一處理邊界讓x21和y21的操作永遠(yuǎn)在數(shù)組范圍內(nèi)避免繁瑣的越界檢查。我早期因?yàn)閺?開始下標(biāo)處理邊界條件時(shí)bug頻出切換到1-base后代碼清爽度和正確率大幅提升。差分?jǐn)?shù)組的初始化如果初始矩陣不是全零如何構(gòu)建初始的差分?jǐn)?shù)組d有兩種等價(jià)的方法方法A公式法直接套用公式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]。注意對(duì)于i1或j1的邊界a[0][*]和a[*][0]視為0。方法B操作法將差分?jǐn)?shù)組d初始化為全零。然后遍歷每個(gè)(i, j)執(zhí)行add(i, j, i, j, a[i][j])。這種方法概念上更統(tǒng)一所有變化都通過add操作完成但效率略低O(n*m)次add調(diào)用每次是O(1)。在大多數(shù)情況下兩種方法都可以我個(gè)人更偏愛方法B因?yàn)檫壿嫾兇獠灰壮鲥e(cuò)。前綴和與差分的互逆性驗(yàn)證在調(diào)試時(shí)一個(gè)很好的方法是先構(gòu)造一個(gè)小的測試用例比如3x3矩陣手動(dòng)計(jì)算其差分矩陣d。然后對(duì)d做前綴和看是否能還原出原矩陣a。接著做一個(gè)區(qū)域修改手動(dòng)更新d的四個(gè)點(diǎn)再求前綴和檢查目標(biāo)區(qū)域是否正確增加了c非目標(biāo)區(qū)域是否不變。這個(gè)手算過程能極大加深你對(duì)公式和邊界條件的理解。擴(kuò)展到“減”操作和更復(fù)雜的運(yùn)算差分不僅限于“加一個(gè)常數(shù)c”。只要運(yùn)算滿足可逆性和結(jié)合律并且區(qū)間修改對(duì)單點(diǎn)的影響是獨(dú)立的就可以應(yīng)用差分思想。例如給一個(gè)區(qū)間乘以一個(gè)常數(shù)、進(jìn)行位運(yùn)算如異或等。對(duì)于“乘一個(gè)常數(shù)k”其差分操作會(huì)有所不同需要重新推導(dǎo)公式。最保險(xiǎn)的還是回歸本質(zhì)思考在差分?jǐn)?shù)組上如何操作才能使得前綴和的結(jié)果是原數(shù)組每個(gè)元素乘以k。性能與空間考量二維差分將區(qū)域修改的復(fù)雜度從 O(矩形面積) 降到了 O(1)。預(yù)處理構(gòu)造差分?jǐn)?shù)組是 O(nm)最終重建矩陣也是 O(nm)。在修改操作遠(yuǎn)多于查詢操作或者修改操作非常密集時(shí)優(yōu)勢(shì)巨大?？臻g上需要額外一個(gè)(n2)*(m2)的數(shù)組通常是可以接受的。在內(nèi)存極其緊張的情況下可以考慮用一維數(shù)組模擬二維或者如果修改和查詢是離線的可以使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)如二維樹狀數(shù)組或二維線段樹但它們單次操作復(fù)雜度是 O(log n * log m)代碼也復(fù)雜得多。二維差分在允許離線處理先收集所有修改最后統(tǒng)一詢問的問題中通常是首選的最優(yōu)解。掌握二維差分后你會(huì)發(fā)現(xiàn)很多看似復(fù)雜的網(wǎng)格更新問題其核心都逃不出這個(gè)模型。它是我個(gè)人認(rèn)為必須熟練掌握的基礎(chǔ)算法思想之一其重要性不亞于排序和二分查找。通過反復(fù)練習(xí)將這四個(gè)點(diǎn)的修改操作和二維前綴和的遞推公式變成肌肉記憶你在處理矩陣類問題時(shí)會(huì)感到游刃有余。