根號分治

前言

因為覺得這個思想很有意思，最近也見到了許多使用根號分治的題目，自己也出了一些用根號分治的題目，所以想總結一下。

（~~下文各種根號分治的名字是我掰出來的，應該有別的稱呼~~）

對文章的細節有疑問或是發現錯誤的歡迎提出。

介紹

根號分治是一種在對資料規模分類討論的基礎上利用不同演演算法平衡複雜度的思想。

根號分治的思想非常樸素，舉個例子：

對於一個 \(n\le 10^9\) 的題目，小明想出了一個能過 \(n\ge 10^4\) 的暴力，小紅想出了一個能過 \(n\le 10^4\) 的暴力，那麼如果他們開黑，將這兩個暴力合在一起過了題，那麼我們就可以說他們使用根號分治通過了這道題，是一種優秀的做法。

從上例可以看出，根號分治的重點在於分治，而不是根號，根號只是在部分情況下複雜度的形式。

根號分治的本質是平衡複雜度，這裡的複雜度包括時間複雜度和空間複雜度，根號分治可以實現時間和空間之間的轉化。

根號分治有一個重要特點：和一定。這裡的和的型別多種多樣，比如字串的長度和，點的度數和，點對的距離和等等。

因為和的型別多種多樣，因此根號分治的應用場景十分廣闊。（~~為什麼什麼東西都能根分~~）

接下來你將會見到一些不同型別根號分治的基礎應用和擴充套件應用。

應用

度數根號分治
給出一張 \(n\) 個點，\(m\) 條邊的無向圖，每個點有點權，進行 \(q\) 次操作，操作分兩種：

將點 \(x\) 的點權增加 \(k\)。

查詢與點 \(x\) 直接相連的點的點權和。
\(1\le n,m,q \le 10^5\)。

這道題可以說是根號分治最經典的題目之一了，我們按照根號分治的過程分析。

首先，我們需要找到一個東西，滿足它的和一定，在這道題中，我們發現給出的是一個一般無向圖，沒有什麼好的性質……嗎？

因為邊數為 \(m\)，一條邊會使得其兩個頂點的度數增加 \(1\)，因此所以點的度數和是 \(O(m)\) 的！

那麼我們考慮根據點的度數進行根號分治，按照套路，設定一個閾值 \(B\)，我們將點按度數大小分為 \(\ge B\) 和 \(< B\) 兩類，分別稱為重點（大度數點）和輕點（小度數點）。

因為點的度數和為 \(m\)，因此我們發現一個重要性質：重點的個數不會超過 \(\dfrac{m}{B}\)，這也是根號分治最重要的性質，即在確定閾值後，大於閾值的個數不會超過資料規模與閾值的比。

我們對於每個重點都維護與其直接相連的點的點權和，記做 \(v\)，接下來對操作和點的型別分類討論：

操作 \(1\)：

直接將點 \(x\) 的點權加 \(k\)，並掃一遍與 \(x\) 直接相連的重點 \(y\)，更新 \(v_y\)。

重點操作 \(2\)：

直接輸出 \(v_x\)。

輕點操作 \(2\)：

暴力掃一遍所有與 \(x\) 直接相連的點，計算答案。

分析一下複雜度，單次第 \(1\) 類的時間複雜度是 \(O(\dfrac{m}{B})\) 的，因為重點個數是這個級別，對重點操作 \(2\) 是 \(O(1)\) 的，對輕點操作 \(2\) 是 \(O(B)\) 的，因為輕點的度數不會超過 \(B\)，因此，總時間複雜度為 \(O(qB+q\dfrac{m}{B})\)，根據我們小學二年級學習的均值不等式，當 \(qB=q\dfrac{m}{B}\)，也就是 \(B=\sqrt m\) 時時間複雜度取到最小值，最小值為 \(O(q\sqrt m)\)。

我們說了這麼久的根號終於出現了！

時空平衡根號分治
有 \(n\) 個集合，集合中元素個數和為 \(m\)，進行 \(q\) 次詢問，每次詢問兩個集合交集的元素個數。
\(1\le n,m,q\le 10^5\)。

我們都知道有一個東西叫做 bitset，我們直接開 \(n\) 個大小為 \(m\) 的 bitset，對於一個集合，若一個數存在，那麼對應位就是 \(1\)，否則是 \(0\)。

在詢問時，我們直接將這兩個詢問的集合的 bitset 與一下，再數一下 \(1\) 的個數就可以了。

讓我們看看複雜度，時間複雜度是 \(O(\dfrac{nm}{w})\) 的，可以通過，但空間複雜度是 \(O(nm)\) 的……

我們發現 bitset 中的 \(1\) 相當稀疏，空間浪費的很嚴重，怎麼辦呢？根號分治！

套路的，設定閾值為 \(B\)，我們只對所有元素個數 \(\ge B\) 的集合開 bitset，那麼 bitset 的個數不會超過 \(\dfrac{m}{B}\)，這樣空間就可以接受了。

詢問時，我們將元素個數小於 \(B\) 的集合中的元素先放入一個公用 bitset 中，再與另一個集合的 bitset 與。

那麼這樣操作下來，時間複雜度變成了 \(O(qB+\dfrac{nm}{w})\)，空間複雜度是 \(O(\dfrac{nm}{B})\)，當 \(B\) 取一個合適的值的時候就可以通過了。

從這個例子中，我們看出了根號分治平衡時空複雜度的強大能力。

分類根號分治
統計 \([l,r]\) 中滿足以下條件的數的個數：

數位中含有 \(k\) 個連續的數位 \(b\)。

可以被 \(x\) 整除。
多測，\(1\le l \le r\le 10^{11},1\le x\le 10^{11},1\le T\le 10\)。

（~~所謂分類根號分治，就是暴力 + 暴力 = 正解~~）

就跟我們在文章開頭舉的例子一樣，我們設定一個閾值 \(B\)，當某個資料範圍小於 \(B\) 時我們使用一種暴力，否則使用另一種暴力。

當 \(x \ge B\) 時，我們發現可以暴力列舉 \(x\) 的倍數並暴力判斷是否合法，時間複雜度為 \(O(T\dfrac{V\log V}{B})\)，其中 \(V=10^{11}\)。

當 \(x < B\) 時，我們考慮數位 DP（這個問題看起來就很數位 DP 不是嗎）。

設計函數 dfs(pos, limit, have, rem, cnt) 表示當前考慮到第 \(pos\) 位，是否緊貼上界（\(limit\)），是否符合有 \(K\) 個 \(B\) 的條件（\(have\)），當前對 \(X\) 的餘數為 \(rem\)，當前已經有 \(cnt\) 個連續的 \(B\) 的方案數，直接記搜即可。

具體的說，考慮記憶化陣列 \(f_{pos,have(0/1),rem,cnt}\)，轉移為

\[f_{pos,have,rem,cnt}=\sum_{o=0}^{up}\begin{cases}f_{pos-1,have\lor[(cnt+1)\ge K],(10rem+o)\bmod X,cnt+1}&o=B\\f_{pos-1,have,(10rem+o)\bmod X,0}&o\not =B\end{cases} \]

其中，\(up\) 表示當前的數位上限，當 \(limit\) 為 \(1\) 時其值為當前 DP 上界的十進位制表示的第 \(pos\) 位，否則為 \(9\)。

時間複雜度為 \(T\times O(B\lg^2V)\times O(\lg V)=O(TB\lg^3 V)\)。

那麼我們的總複雜度就是 \(O(T(\dfrac{V\lg V}{B}+B\lg^3 V))\)，還是使用均值不等式，得出當 \(B\) 取 \(\dfrac{\sqrt V}{\lg V}\approx28,748\) 時最優，為 \(O(T\sqrt V\lg^2V)\approx 4\times 10^8\)，由於常數比較小所以可以通過。

空間複雜度為 \(O(B\lg^2V)=O(\sqrt V\lg V)\approx 3.5\times 10^6\)，可以接受。

事實上，分類根號分治是最常用的根號分治方法之一，平衡兩種暴力的複雜度的思想是非常重要的。

本質上，分類根號分治利用的是資料範圍的和一定的性質。（~~這也算性質~~）

餘數根號分治
維護一個長為 \(n\) 序列 \(a\)，進行 \(q\) 次操作，操作分以下兩種：

將 \(a_x\) 增加 \(k\)。

查詢所有下標模 \(x\) 的餘數為 \(k\) 的所有數的和。
\(1\le n,q\le 10^5\)。

（事實上，這個類別應該歸入分類根號分治中，但因為比較常見就單獨拎出來了）

因為這也是分類根號分治的一種，因此我們考慮兩種暴力：

直接修改，查詢時從 \(k\) 開始列舉，每次 \(+x\)，求和。
設 \(f_{i,j}\) 表示下標模 \(i\) 的餘數為 \(j\) 的所有數的和，修改時 \(O(n)\) 更新 \(f\) 陣列，查詢時直接查表輸出。

我們發現，這兩種暴力分別對應了兩種極端：一種是 \(O(1)\) 修改，\(O(n)\) 查詢，另一種是 \(O(n)\) 修改，\(O(1)\) 查詢。

那麼我們還是按照老套路，將這兩種暴力合併。

設定閾值為 \(B\)，對應 \(x>B\) 的查詢我們直接按照做法 \(1\) 的做法暴力做，時間複雜度為 \(O(q\dfrac{n}{B})\)。

同時，我們依舊開一個表，但我們只開 \(B\times B\) 大小的，也就是說，設 \(f_{i,j}\) 表示下標模 \(i\) 的餘數為 \(j\) 的所有數的和，其中 \(j\le i \le B\)。那麼對於 \(x\ge B\) 的查詢我們依舊可以查表，這樣查詢就搞定了。

修改時，因為我們只開了 \(B\times B\) 的表，因此單次改表的複雜度是 \(O(B)\) 的。

算下來，總時間複雜度為 \(O(q(B+\dfrac{n}{B}))\)，空間複雜度為 \(O(B^2)\)，容易得到當 \(B\) 取 \(\sqrt n\) 時複雜度最優，為 \(O(q\sqrt n)\)。

模根號分治常見於資料結構題中，跟下文的步長根號分治有一定的相似性。

顏色根號分治
給定一個 \(n\times n\) 的網格，每個點有一個顏色 \(a_i\)，統計有多少條路徑滿足以下條件：

起點和終點的顏色相同。

只能向下或向右走。
\(1\le n\le 500,1\le a_i\le n^2\)。

首先，我們需要找到和一定的東西，在顏色根號分治中，和一定的是點的數量（~~這不是廢話嗎~~），或者換句話說，是所有顏色的點的數量和。

先別管那麼多，我們設定閾值為 \(B\)，如果某種顏色的點的數量大於 \(B\)，那麼我們將這種顏色稱為重顏色，否則稱為輕顏色。我們容易發現，重顏色的種數不會超過 \(O(\dfrac{n^2}{B})\)。

對於這道題，我們對每種顏色獨立考慮，對當前考慮的顏色是輕還是重分類討論。

如果當前是輕顏色，那麼我們直接雙重列舉該顏色的所有點，對於一對點 \((x_1,y_1),(x_2,y_2)\)，其能產生的路徑數量顯然是 \({x_2-x_1+y_2-y_1\choose x_2-x_1}\)。
如果當前是重顏色，我們發現還有一種 DP 做法可以統計路徑數量。

設 \(f_{i,j}\) 表示以 \((i,j)\) 結尾的路徑數量，那麼有：\(f_{i,j}=f_{i-1,j}+f_{i,j-1}+a_{i,j}\)，其中，\(a_{i,j}\) 在點 \((i,j)\) 的顏色時當前顏色時其值為 \(1\)，否則為 \(0\)。

分析一下複雜度，重顏色的數量不會超過 \(\dfrac{n^2}{B}\)，對於每一種重顏色我們都做一遍 \(O(n^2)\) 的 DP，這部分的複雜度是 \(O(\dfrac{n^4}{B})\)。

輕顏色的數量是 \(O(n^2)\) 級別的，而輕顏色的點的數量是 \(O(B)\) 級別的，看似總複雜度為 \(O(n^2B^2)\) 的，但考慮到一個點最多被列舉 \(B\) 次，因此這部分的複雜度實際上是 \(O(n^2B)\)。

那麼總複雜度是 \(O(n^2B+\dfrac{n^4}{B})\)，還是用熟悉的均值不等式，得出當 \(B=n\) 時複雜度最優，時間複雜度為 \(O(n^3)\)。

顏色根號分治也是常見的根號分治，經常會結合一些奇怪的東西一起考察。

步長根號分治
給定一顆 \(n\) 個點的帶邊權樹，邊權為 \(1\) 或 \(2\)，多次詢問，問在從點 \(u\) 出發到點 \(v\)，一次可以走 \(k\) 的距離的情況下最少要走幾步。
\(1\le n\le 10^5,1\le k\le n\)。

步長根號分治利用的是兩點之間距離一定的性質。

設定閾值為 \(B\)（~~萬能的套路~~），那麼我們發現當 \(k> B\) 時，我們最多跳 \(\dfrac{n}{B}\) 步，而跳一步可以用樹剖 + 二分實現（找到最後的重鏈，在重鏈上二分，需要預處理距離），是 \(O(\log n)\) 的，這部分的時間複雜度為 \(O(nB\log n)\)。

當 \(k\ge B\) 時，我們預處理 \(f_{i,c,j}\)，表示從點 \(i\) 出發，在一次跳 \(c\) 的距離的情況下跳 \(2^j\) 次步跳到的點。

這個東西可以之間倍增處理，也就是 \(f_{i,c,j} = f_{f_{i,c,j-1},c,j-1}\)，而 \(f_{i,c,0}\) 可以用上述所說的樹剖 + 二分求出。

那麼單次詢問時我們從 \(u,v\) 分別往上倍增跳，跳到不超過其 LCA 的最遠點，再判斷一下最後的距離要跳一次還是跳兩次即可。

步長根號分治可以看作餘數根號分治的擴充套件。不過做法的細節還是比較多的。

總結

除了上述幾大類根號分治之外，還有一些比較特別的根號分治，比如質因子根號分治，斜率優化根號分治等等，但因為泛用性不廣，故不一一列出。

總的來說，根號分治是一種常見的思想，在 OI 中佔有一席之地，在遇到可以找出某個東西和一定的題目時可以想想根號分治。

涉及到平衡複雜度的演演算法並不多，主要就是一眾根號演演算法（根分，分塊，莫隊），當複雜度不平衡時可以往這邊想一想。

前言

介紹

應用

總結

更多題目