模型1：區(qū)間加法，單點(diǎn)詢問(wèn)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及區(qū)間加法，單點(diǎn)查值。

對(duì)每個(gè)塊設(shè)置一個(gè)加法標(biāo)記，記錄這個(gè)塊中元素一共加了多少，每次操作對(duì)整塊直接 O(1) 標(biāo)記，而不完整塊元素較少，暴力修改元素的值即可，每次詢問(wèn)時(shí)返回元素的值加上其所在塊的加法標(biāo)記。

模型2：區(qū)間加法，詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的元素個(gè)數(shù)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及區(qū)間加法，詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的元素個(gè)數(shù)。

對(duì)于區(qū)間操作，其實(shí)只有三項(xiàng)東西需要思考：

• 要預(yù)處理的信息
• √n?個(gè)整塊的處理
• 不完整塊的 2√n?個(gè)元素的處理

考慮詢問(wèn)的情況：對(duì)于不完整的塊的 2√n?個(gè)元素，直接枚舉統(tǒng)計(jì)即可，而在整塊內(nèi)尋找小于某個(gè)值的元素，暴力枚舉的時(shí)間復(fù)雜度過(guò)高，因此考慮使用二分查找，這就要求塊內(nèi)元素是有序的，因此需要在預(yù)處理時(shí)對(duì)每塊做一遍排序，每次查詢?cè)?√n 個(gè)塊內(nèi)二分，然后暴力不完整塊的 2√n 個(gè)元素即可

再考慮區(qū)間操作的情況：區(qū)間操作仍為區(qū)間加法，這樣就可以套用 模型 1 的方法，維護(hù)一個(gè)加法標(biāo)記，但不同的地方在于，不完整塊修改后，可能會(huì)使得該塊內(nèi)數(shù)字亂序，所以頭尾兩個(gè)不完整塊需要進(jìn)行重新排序

這樣一來(lái)，在加法標(biāo)記下的詢問(wèn)操作，在塊外暴力查詢小于 (x-加法標(biāo)記) 的元素個(gè)數(shù)，塊內(nèi)使用 (x-加法標(biāo)記) 作為二分查找的值即可

模型3：區(qū)間加法，詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的前驅(qū)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及區(qū)間加法，詢問(wèn)區(qū)間內(nèi)小于某個(gè)值 x 的前驅(qū)。

所謂前驅(qū)，是指對(duì)于某個(gè)值 x ，比其小的最大元素

該模型可以延續(xù) 模型 2 的方法，將塊內(nèi)查詢的二分進(jìn)行修改，由于是要找的是 x 的前驅(qū)，因此暴力找左右不完整塊的比 x 小最大值，再二分找整塊比 x 小的最大值，取其中最大即可

模型4：區(qū)間加法，詢問(wèn)區(qū)間和

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及區(qū)間加法，詢問(wèn)區(qū)間和。

相較于 模型 1 來(lái)說(shuō)，該模型只是將單點(diǎn)詢問(wèn)改為了區(qū)間詢問(wèn)，不完整塊仍是需要暴力，而要快速統(tǒng)計(jì)整塊的答案，需要維護(hù)每個(gè)塊的元素和，這就需要進(jìn)行預(yù)處理。

在預(yù)處理時(shí)：求得每個(gè)塊內(nèi)的和，修改時(shí)對(duì)于邊角料暴力修改值，修改了 a[i] 的值同時(shí)也要把 a[i] 所在塊的值修改，對(duì)于中間的 k 塊，修改標(biāo)記 tag[i]，表示第 i 個(gè)塊加上了 tag[i]，簡(jiǎn)單來(lái)說(shuō)，即整塊用一個(gè) ans 數(shù)組來(lái)維護(hù)整塊的和，不完整的塊直接暴力加

在詢問(wèn)時(shí)：在 tag 里記下對(duì)于一個(gè)塊一共加上了多少，然后對(duì)于邊角料的處理與模型 1 類似，暴力+a[i]+tag[pos[i]]，對(duì)于中間的 k 塊，加上 ans[i]，因?yàn)槠渲杏?block 個(gè)數(shù)，因此要加 block 個(gè) tag[i]

模型5：區(qū)間開(kāi)方，詢問(wèn)區(qū)間和

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，數(shù)列中的元素最大為 2^31-1，以及 n 個(gè)操作，操作涉及區(qū)間開(kāi)方，詢問(wèn)區(qū)間和。

由于在整塊開(kāi)方時(shí)，必須要知道每一個(gè)元素才能知道他們開(kāi)方后的和，難以快速的對(duì)一個(gè)塊進(jìn)行信息更新，但不難發(fā)現(xiàn)，修改操作只有向下取整開(kāi)方，而一個(gè)數(shù)經(jīng)過(guò)幾次開(kāi)方后，其值最終會(huì)變成 1

因此，如果每次區(qū)間開(kāi)方只涉及不完整塊，那么仍然對(duì) 2√n 個(gè)元素直接暴力‘；如果涉及到整塊，由于這些塊經(jīng)過(guò)若干次操作后都變?yōu)?1，此時(shí)可采用一種分塊優(yōu)化的暴力，即只要每個(gè)整塊開(kāi)方后，記錄元素是否都變成了 1，這樣在區(qū)間修改時(shí)，可以設(shè)置一個(gè) flag 數(shù)組，用于標(biāo)記塊中元素是否全為 1，若是，則跳過(guò)那些全為 1 的塊即可，若不是，則對(duì)塊中元素進(jìn)行暴力，由于數(shù)列中的元素最大為?2^31-1，因此最多開(kāi)方 5 次后就為 1，時(shí)間復(fù)雜度在允許范圍之內(nèi)

模型6：單點(diǎn)插入，單點(diǎn)詢問(wèn)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，操作涉及單點(diǎn)插入，單點(diǎn)詢問(wèn)，數(shù)據(jù)隨機(jī)生成。

可以在塊內(nèi)維護(hù)數(shù)組以為的數(shù)據(jù)結(jié)構(gòu)使其更具有拓展性，比如在每個(gè)塊內(nèi)存放?vector、set、multiset 等數(shù)據(jù)結(jié)構(gòu)?，這樣如果還有插入、刪除元素的操作，會(huì)更加的方便。

對(duì)于本模型來(lái)說(shuō)，數(shù)據(jù)是隨機(jī)生成的，可以在每塊內(nèi)維護(hù)一個(gè) vector，每次插入時(shí)找到位置所在的塊，再暴力插入，將塊內(nèi)其他元素直接向后移動(dòng)一位，這樣來(lái)實(shí)現(xiàn)插入操作，時(shí)間復(fù)雜度不會(huì)太高。

但對(duì)于數(shù)據(jù)不是隨機(jī)的情況，如果在一個(gè)塊內(nèi)有大量的單點(diǎn)插入，會(huì)使得這個(gè)塊的大小超過(guò) √n，這樣對(duì)塊內(nèi)暴力的復(fù)雜度就沒(méi)有保證了，此時(shí)需要引入一個(gè)新的操作：重構(gòu)，即重新分塊。

重構(gòu)，是每 √n 次插入后，重新將數(shù)列進(jìn)行分塊，由于重構(gòu)所需的時(shí)間復(fù)雜度為 O(n)，重構(gòu)次數(shù)為 √n，因此重構(gòu)的時(shí)間復(fù)雜度沒(méi)有問(wèn)題，且保證了每個(gè)塊的大小相對(duì)均衡。

模型7：區(qū)間乘法與加法，單點(diǎn)詢問(wèn)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，操作涉及區(qū)間乘法，區(qū)間加法，單點(diǎn)詢問(wèn)。

顯然，如果只有區(qū)間加法或區(qū)間乘法，那么與 模型 1 沒(méi)有本質(zhì)區(qū)別，但當(dāng)兩者同時(shí)出現(xiàn)，需要考慮如何同時(shí)維護(hù)兩種標(biāo)記。

對(duì)于整塊來(lái)說(shuō)，由于加法操作會(huì)影響乘法操作的值，因此令乘法標(biāo)記的優(yōu)先級(jí)高于加法標(biāo)記的優(yōu)先級(jí)，則有：

• 若當(dāng)前的一個(gè)塊乘以 m1 后加上 a1，此時(shí)再進(jìn)行一個(gè)乘以 m2 的操作，那么原來(lái)的標(biāo)記變?yōu)?#xff1a;m1*m2、a1*m2
• 若當(dāng)前的一個(gè)塊乘以 m1 后加上 a1，此時(shí)再進(jìn)行一個(gè)加上?a2 的操作，那么原來(lái)的標(biāo)記變?yōu)?#xff1a;m1，a1+a2

因此，可以用 addTag[i] 來(lái)存放第 i 個(gè)整塊的加數(shù)，mulTag[i] 存放第 i 個(gè)整塊的系數(shù)，當(dāng)一個(gè)整塊進(jìn)行乘法操作乘以 x 時(shí)，兩個(gè)標(biāo)記都要乘以 x，即：addTag[i]=addTag[i]*x，mulTaf[i]=mulTag[i]*x

對(duì)于不完整塊來(lái)說(shuō)，由于前面的操作可能將其當(dāng)作完整塊處理，因此每次不完整塊都要更新為最新的值后再進(jìn)行暴力

模型8：詢問(wèn)區(qū)間某值個(gè)數(shù)，區(qū)間賦值

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，操作涉及區(qū)間詢問(wèn)等于一個(gè)數(shù) x?的元素，并將這個(gè)區(qū)間的所有元素改為 x。

區(qū)間賦值沒(méi)有什么難度，但區(qū)間查詢比較難，因?yàn)闄?quán)值種類比較多，似乎沒(méi)有什么好的維護(hù)方法

但通過(guò)模擬一些數(shù)據(jù)可以發(fā)現(xiàn)，詢問(wèn)后一整段區(qū)間都會(huì)被修改，幾次詢問(wèn)后數(shù)列可能就只剩下若干個(gè)不同的區(qū)間了

考慮使用 模型 5 的方法，采用分塊優(yōu)化的暴力，建立一個(gè)標(biāo)志數(shù)組，在維護(hù)每個(gè)整塊的時(shí)候，判斷該塊是否只有一種權(quán)值，這樣在區(qū)間操作的時(shí)候，對(duì)于同權(quán)值的一個(gè)塊能在 O(1) 即可統(tǒng)計(jì)答案，若不是只有一種權(quán)值，那么就暴力統(tǒng)計(jì)答案，然后修改標(biāo)記，而對(duì)于不完整塊，同樣使用暴力維護(hù)

這樣一來(lái)，最差的情況每次都會(huì)消耗 O(n) 的時(shí)間，但實(shí)際上，可以這樣進(jìn)行分析：假設(shè)初始序列都是同一個(gè)值，那么查詢是 O(√n)，如果此時(shí)進(jìn)行一個(gè)區(qū)間操作，其最多破壞首尾兩個(gè)塊的標(biāo)記，因此只能使后面的詢問(wèn)至多多兩個(gè)塊的暴力時(shí)間，因此均攤后每次操作的復(fù)雜度仍為 O(√n)，簡(jiǎn)單來(lái)說(shuō)，要想讓一個(gè)操作花費(fèi) O(n) 的時(shí)間，就要先花費(fèi) √n 個(gè)操作對(duì)數(shù)列進(jìn)行修改

模型9：詢問(wèn)區(qū)間眾數(shù)

問(wèn)題：給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及詢問(wèn)區(qū)間的最小眾數(shù)。

分塊算法的優(yōu)越性之一在于能詢問(wèn)區(qū)間眾數(shù)，這是線段樹(shù)解決不了的問(wèn)題

對(duì)于 n 個(gè)數(shù)的序列，首先進(jìn)行分塊，預(yù)處理兩塊之間的眾數(shù)，將兩塊間的最小眾數(shù)記錄下來(lái)，然后再進(jìn)行查詢

在每次查詢時(shí)，首先將中間的整塊的眾數(shù)記錄下來(lái)，然后再依次處理左邊角料和右邊角料，二分尋找是否能夠更新，最后處理完成后，返回尋找到的值即可

值得注意的是，在進(jìn)行分塊時(shí)，有時(shí)題會(huì)卡常數(shù)，即將塊分為 √n 時(shí)仍會(huì) TLE，此時(shí)需要用兩塊分塊大小不同的代碼對(duì)拍，根據(jù)運(yùn)行時(shí)間來(lái)不斷調(diào)整分塊大小，以減少常數(shù)

總結(jié)

以上是生活随笔為你收集整理的线性结构 —— 分块算法 —— 分块九讲的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。