手機(jī)站首頁(yè)散文詩(shī)歌雜文隨筆日記小小說(shuō)

散文網(wǎng) » 科技 »學(xué)習(xí) » C++ 基礎(chǔ)算法 - 二維差分

C++ 基礎(chǔ)算法 - 二維差分

2023-07-21 23:39 作者:DecemberFox 0人讀過(guò) | 我要投稿

今天學(xué)習(xí)二維差分。

一維差分

在學(xué)習(xí)二維差分之前，先要學(xué)會(huì)?一維差分

這里加強(qiáng)對(duì)一維差分的理解

將一位差分的操作變?yōu)榍熬Y的變化，如下列數(shù)列 ( 從 0 開(kāi)始編號(hào) )

將 2 至 5 的數(shù)字 ( 對(duì)應(yīng)數(shù)列中 7，8，2，1?) 增加 $k$ ，且 $k%3D4$ ，那么差分?jǐn)?shù)組從全為 0 變?yōu)?/p>

此時(shí)差分?jǐn)?shù)組的前綴和將分為三段 ( 相較于原來(lái)全為 0 的差分?jǐn)?shù)組?)

第一段為 0 至 1 ( 對(duì)應(yīng)數(shù)列中 9，4 ) 的前綴和不變，仍然為 0
第二段為 2 至 5 ( 對(duì)應(yīng)數(shù)列中 7，8，2，1 ) 的前綴和增加了 4
第三段為 6 至 7 ( 對(duì)應(yīng)數(shù)列中?0，3 ) 的前綴和不變，4 與 -4 相互抵消

正好對(duì)應(yīng)了將 2 至 5 的數(shù)字增加 4 的概念

因此我們可以知道，差分?jǐn)?shù)組中每一位的前綴和表示的就是原數(shù)列該位置的增值

即? $a_i(%E4%BF%AE%E6%94%B9%E5%90%8E)%3Da_i(%E4%BF%AE%E6%94%B9%E5%89%8D)%2Bsumdiff_%7Bi%7D$ ， $sumdiff_i$ 表示的是差分?jǐn)?shù)組? $diff$ 的前綴和，轉(zhuǎn)化后可得? $sumdiff_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)$ ，修指修改后的，原指原來(lái)的

所以每一位的增值? $p_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)%3Dsumdiff_i$ ，這就使用數(shù)學(xué)的方法解釋了差分?jǐn)?shù)組的作用，最后我們得到了這樣的式子

$p_i%3Dsumdiff_i%3Da_i(%E4%BF%AE)-a_i(%E5%8E%9F)$

這樣看起來(lái)差分的復(fù)雜度只有一次修改的復(fù)雜度? $O(1)$ ?,修改 $k$ 次，復(fù)雜度也僅有 $O(k)$ 次，看起來(lái)時(shí)間復(fù)雜度十分好，但是如果算上查詢 $m$ ?次，復(fù)雜度變?yōu)? $O(k%2Bmn)$ ，并不高效

因此差分僅適合在數(shù)據(jù)范圍較小的題目使用，遇到數(shù)據(jù)范圍更加大的題目時(shí)就需要使用復(fù)雜度為? $O(klog_2n%2Bmlog_2n)$ ?的樹(shù)狀數(shù)組和線段樹(shù)來(lái)實(shí)現(xiàn)了，但因?yàn)椴罘志幋a簡(jiǎn)單，在適合的時(shí)候往往選擇容易編寫(xiě)的差分

二維差分

由一維差分可以知道，二維差分就是選擇一個(gè)矩形區(qū)域，將區(qū)域內(nèi)的所有元素增加或減少一個(gè)數(shù)? $t$

簡(jiǎn)單做法 ( 并不正確 )

本段通過(guò)思考簡(jiǎn)單的做法推動(dòng)二維差分實(shí)現(xiàn)，因此本段不是正解，可以選擇性閱讀本段

修改

先考慮將矩形區(qū)域處理一下，變?yōu)橐粭l條數(shù)列的區(qū)間從而使用普通一位差分修改

如上圖，將? $A(x_a%2Cy_a)$ ?至 $D(x_d%2Cy_d)$ ?的值加上? $t$ ，再將? $C(x_c%2Cy_c)$ 至? $B(x_b%2Cy_b)$ 修改為? $-t$ ，復(fù)雜度為? $O(height_%7B%E4%BF%AE%E6%94%B9%7D)$

查詢

在查詢時(shí)，如果詢問(wèn)的矩形區(qū)域 (? $%E7%9F%A9%E5%BD%A2_%7BA'B'C'D'%7D$ ?) 正好沒(méi)有與修改矩形區(qū)域 (? $%E7%9F%A9%E5%BD%A2_%7BACBD%7D$ )，的左邊線 (? $AD$ ) 相交，這時(shí)在統(tǒng)計(jì)時(shí)就無(wú)法加上修改矩形區(qū)域修改的值，因此，我們不能從詢問(wèn)的矩形區(qū)域的左邊線 (? $A'C'$ )，開(kāi)始計(jì)算，應(yīng)該從其對(duì)應(yīng)在? $y$ ?軸上的點(diǎn)? $A''$ 與? $C''$ 開(kāi)始計(jì)算

這種方式將每一行都看做一個(gè)差分?jǐn)?shù)組，都做了一次差分，時(shí)間復(fù)雜度為? $O(height_%7B%E6%9F%A5%E8%AF%A2%7Dx_%7B%E6%9F%A5%E8%AF%A2%7D)$

不難發(fā)現(xiàn)，這種方法的時(shí)間復(fù)雜度比較劣，還有提升的空間

正確做法

本段講解的才是正確的二維差分

修改

我們嘗試將修改操作的復(fù)雜度降至? $O(1)$ ，我們知道一維差分可以將所有? $a_i$ ?(? $l%5Cle%20i$ ?) 的數(shù)值增加 $t$ ，通過(guò)兩次修改實(shí)現(xiàn)區(qū)間修改

將這個(gè)思想推廣至二維，那么二維差分就應(yīng)該可以將所有? $a_%7Bi%2Cj%7D$ (? $x_l%5Cle%20i%2Cy_l%5Cle%20j$ ) 的數(shù)值增加? $t$

例如上面三連展示的圖片，我們將右下角看做原點(diǎn)， $%E7%9F%A9%E5%BD%A2_%7BBCAD%7D$ ?是要修改的矩形區(qū)域，這時(shí)候我們將上一段所述的? $x_l%3Dx_B%2Cy_l%3Dy_B$ ，那么點(diǎn) B 左上的所有點(diǎn)都增加了 $t$ ，但是我們更改的目標(biāo)是? $%E7%9F%A9%E5%BD%A2_%7BBCAD%7D$ ，如果使用上述方法將會(huì)更改整一個(gè)? $%E7%9F%A9%E5%BD%A2_%7BOFBH%7D$ ，而如果要消除影響，就可以將? $%E5%A4%9A%E8%BE%B9%E5%BD%A2_%7BOFCADH%7D$ ?再次減去 $t$

看看這個(gè)多邊形的樣子，是不是很熟悉

所以，我們以右上角為原點(diǎn)并加入二維前綴和的思想，并利用公式

$sum_%7Bx_b%2Cy_b%7D%3Dsum_%7Bx_b%2Cy_a-1%7D%2Bsum_%7Bx_a-1%2Cy_b%7D-sum_%7Bx_a-1%2Cy_a-1%7D$

上述公式在?二維前綴和?中講過(guò)了

這時(shí)候我們需要反過(guò)來(lái)使用，因?yàn)槲覀兿葎?chuàng)造了 $sum_%7Bx_b%2Cy_b%7D$ 的影響 ( 增加? $t$ )，所以我們?cè)诤竺鎸⑾溆绊懀涂梢允褂眠@個(gè)式子，? $sum_%7Bx_b%2Cy_a-1%7D%2Bsum_%7Bx_a-1%2Cy_b%7D-sum_%7Bx_a-1%2Cy_a-1%7D$

這三個(gè)項(xiàng)就是消除的關(guān)鍵，因?yàn)樵黾恿? $t$ ，所以? $sum_%7Bx_b%2Cy_b%7D$ ?的值也就為 $t$ ，因此? $sum_%7Bx_b%2Cy_a%7D$ 與? $sum_%7Bx_a%2Cy_b%7D$ 都要等于? $-t$ ?以消除影響，但是我們發(fā)現(xiàn) $sum_%7Bx_a-1%2Cy_a-1%7D$ 被兩次操作都減了一次 $t$ ，因此需要在? $sum_%7Bx_a-1%2Cy_a-1%7D$ ?再加上一次 $t$ ，這其實(shí)就是前綴和的思路