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