分塊思想最根本的部分是「平衡」二字。
以下例題大致按難度排序，但可能有並列
當前版本是大綱，關於題目的分析很可能並不完善。
以及介紹部分可能也不全面/完善，如有疏漏敬請各位讀者指正！
我們需要做的，就是通過設計一個平衡方案，使得我們可以分而在最小的複雜度內解決所有的操作。
大致有兩種應用：
分塊最基礎的表示就是利用時間複雜度的平衡維護序列上的資訊。我們通過對序列的適當的劃分平衡複雜度。正常而言，我們將整個序列劃分為長度為 \(B\) 的塊，最後長度小於 \(B\) 的自成一塊。
複雜度的平衡通過塊資訊的合併完成。
不難發現，對區間的操作可以被拆分為對一系列整塊的操作和對 \(O(1)\) 個散塊的操作。因此我們對散塊實行復雜度大的暴力演演算法，對整塊採用複雜度小的整體標記，即可做到平衡修改的複雜度。同理，我們將整塊的資訊合併，在需要時直接加入整塊資訊，而對散塊可以直接掃描每個元素。
這就做到了複雜度平衡。
在這部分中，分塊常用於替代線段樹，維護一些無法採用線段樹維護的資訊。有時需要處理任意兩塊間的資訊，容易發現這樣的資訊數是 \(O(n)\) 的。
這類問題的例子是最初分塊和第二分塊。
一般來說，值域分塊會作為一個輔助工具出現在題目當中。
值域分塊是權值線段樹的替代，其大多數應用同樣是平衡複雜度：假設我們需要進行 \(O(n\sqrt n)\) 次插入元素，但是隻需要 \(O(n)\) 次查詢，那採用權值線段樹就不能做到整體的平衡了。我們需要 \(O(1)\) 插入 \(O(\sqrt n)\) 查詢的資料結構。這就自然想到值域分塊。
以值域分塊維護集合第 \(k\) 小為例：每個塊上記錄塊內總元素數，每個值的位置記錄該值出現了多少次。插入只需要維護當前位置和所在塊的資訊，因此是 \(O(1)\) 的。查詢時，首先掃描所有塊，找到第 \(k\) 小值所在的塊，再掃描對應塊找到真正的第 \(k\) 小值，因此是 \(O(\sqrt n)\) 的。
值域分塊作為二次平衡的體現，會經常在經過平衡後的演演算法中出現。例子有作業與risrqnis。
常常出現在「不帶修改很可做，但帶了修就都沒法維護了，而且只有修改的話不難維護」的題上。
顧名思義，操作分塊就是對操作序列進行分塊。我們可以將操作塊看作一個資訊簇，在處理完該塊後統一重構。當處理到一塊時，我們已經將操作分成了兩個部分：第一個部分是先前塊內的修改，這些部分已經在實際的資訊點上進行完了，因此這部分是靜態的貢獻。第二個部分是當前塊內的修改，而這些修改總數不會達到塊大小，因此可以樸素地計算這部分的貢獻。
計算後將這兩部分貢獻結合即可得到對應詢問的答案。
操作分塊適用於整體重構複雜度小的資訊，經典例子是單點修改和虛樹。值得注意的是，操作分塊的性質使得它可能出現於優化不可帶修資訊的求解上。這樣的例子有CF925E和第十分塊。
這裡的樹分塊並不是樹上莫隊相關的內容。這裡涉及的樹分塊是將樹分成 \(B\) 個邊集不交的極大子樹，每個聯通塊以關鍵點（通常選聯通塊的 LCA）作為資訊簇的儲存位置。
有兩種樹分塊的形式。
第一種是簡易樹分塊。我們直接隨機 \(B\) 個關鍵點，如果樹根不在其中的話加入樹根。對於每個點，將其與其最深的關鍵祖先放在同一個聯通塊內。這樣做的常數較大，而且有小概率複雜度爆炸。mrsrz 在一篇題解中提及了一種確定性的演演算法，能使得每個點到關鍵點的距離不超過 \(B\)，並且總數不超過 \(\frac nB\)。具體地，我們每次選擇一個深度最大的非關鍵點，然後若它的 \(1\sim S\) 級祖先都不是關鍵點，則我們把它的 \(S\) 級祖先標記為關鍵點。由標記過程可知距離不超過 \(S\)，並且每標記一個關鍵點，至少有 \(S\) 個點不會被標記，所以關鍵點數量也是正確的。
第二種是 top cluster 劃分。具體看 zx2003 的 2021 集訓隊論文，先咕著。
具體地，我們對序列分塊，每塊內部使用類連結串列方式儲存，所有塊鏈首也使用類連結串列方式儲存。這樣我們就得到了一個兩層的連結串列。
為什麼要這麼做呢？眾所周知，連結串列的直接插入刪除速度很快，但是其複雜度瓶頸在於 \(O(n)\) 的定位元素。回顧值域分塊查詢 \(k\) 小的方式。我們發現，將此方式套用在塊狀連結串列結構上，我們就能以 \(O(\sqrt n)\) 的複雜度定位到一個確定元素。這樣我們就得到了 \(O(\sqrt n)\) 複雜度進行修改和查詢的連結串列。
普通連結串列不需要在意在同一個位置插入多次的情況，但是塊狀連結串列需要考慮這個問題。眾所周知，塊大小的平均是分塊演演算法保證複雜度（和常數）的根本。正常的分塊是靜態的，在初始化後不需要刻意地維護塊大小。然而塊大小在塊狀連結串列中是可變的，因此維護塊大小 \(=O(\sqrt n)\) 就變得必要起來。我們需要在塊大小大於 \(2\sqrt n\) 時分裂塊，相鄰兩塊加和 \(\le \sqrt n\) 時合併塊（一般而言不用合併的複雜度正確）。需要使用塊大小漸進相關的維護方法，因此如果維護值域資訊的話需要斟酌，或是採用只需要儲存整塊資訊的值域分塊。
採取以上做法即可將單次操作的複雜度控制在 \(O(\sqrt n)\) 內。
一個 trick 是內層連結串列採用 vector 實現，這樣內層的常數會很小。而且插入複雜度也是 \(O(\sqrt n)\)，不會劣化。
例子是文字編輯器和帶插入區間 K 小值。
這裡 \(n\) 的範圍仍然是 \(10^5\) 的，資訊點集大小 \(=O(n)\)。我們需要維護 \(n\times n\) 的平面。
一維分塊的散塊可以隨便做，但是二維分塊的情況就不是那麼簡單了。這裡的散塊很有可能退化成 \(O(n)\) 甚至更劣的大小。而且直接套用 \(\sqrt n \times \sqrt n\) 的塊長會導致空間急速增加。
這裡討論的資訊是滿足結合律、合併快的資訊，因此每個塊維護的資訊大小預設是 \(O(1)\)。
容易發現一層分塊無論如何都會產生散塊範圍過大的問題。因此考慮分二級塊。我們首先將平面分成 \(\sqrt n\) 個 \(n^{0.75}\times n^{0.75}\) 的一級塊，隨後將每個一級塊分成 \(\sqrt n\) 個 \(n^{0.5}\times n^{0.5}\) 的二級塊。一級塊維護一級塊的二維字首和，二級塊維護所在一級塊內二級塊的二維字首和。這部分的空間複雜度是 \(O(n)\) 的。這樣（部分地）解決了整塊和右上角散塊的問題。
然後考慮右端和上端的散塊。以上端為例。我們將平面橫著分為 \(n\times n^{0.75}\) 的一級塊，塊內分 \(\sqrt n\) 個 \(n^{0.75}\times n^{0.5}\) 的塊。豎著同理。每個塊維護所在區域內塊的二維字首和。
這樣加入點是 \(O(\sqrt n)\) 的。查詢二維字首和整塊是 \(O(1)\) 的。
隨後我們即可發現，每次查詢都會剩餘矩形邊上的一圈範圍，這些範圍的寬度是 \(< n^{0.5}\) 的。這部分只能根據維護的資訊調整。以區間本質不同逆序對為例。應用莫隊後能發現這是二維數點問題，且橫縱座標彼此不同。我們對縱座標分 \(\sqrt n\) 塊，容易發現每種散塊都只會被分到一個塊內，且它們都對應著一個字首。加入資訊點時，更新所在塊內對應可能有貢獻的散塊。能發現每個資訊點對應能貢獻的散塊只有 \(O(n)\) 個，因為滿足條件的散塊都應該覆蓋該點且未覆蓋該點所在 \(n^{0.5}\times n^{0.5}\) 塊右上角位置。因此總時間複雜度為 \(O(n\sqrt n)\) 個。
由於每個散塊資訊都已經在加入時更新完，這就做到了散塊 \(O(1)\) 查詢。
因此有 \(O(\sqrt n) - O(1)\)。
例題：rdiq，博麗靈夢。
關於 \(O(1)-O(\sqrt n)\) 的做法可以看rvrewsus。
展開說一下。
這一類問題的標準 Trick 是分類討論貢獻次數大於/小於 \(\sqrt n\) 的物件，並對這兩個部分根據不同的性質採用不同的方式求出貢獻。或者形式化地，我們需要維護序列 \(s\) 的值域相關資訊，而序列 \(s\) 滿足 \(\sum s_i = n\)。
對於眾數而言是出現次數大於 \(\sqrt n\) 的元素不會超過 \(\sqrt n\) 個，因此可以對每個出現次數大於 \(\sqrt n\) 的元素以 \(O(n)\) 的方式求出貢獻；反之則有元素出現次數小於 \(\sqrt n\)，可以根據出現次數統計答案。例子是眾數。
類似的內容用在圖上也可以，我們可以將度數超過 \(\sqrt m\) 的點和其餘點分離，以類似的思想進行處理。這又被稱作度數分塊。例題有Graph。
另一種我不知道有沒有其他很有趣的應用。具體而言，可以通過一定處理將各操作劃分為不交的貢獻集，分別對這些貢獻集進行處理。這類操作在特定情況下又被稱作按塊離線，使用到這個 trick 的題有第六分塊。另一個例子是 risrqnis，這道題包含好幾個 Trick，是很好的分塊入門例題。Solution
在這裡也提一下貢獻計算的問題。在根號分治題目中，常常出現不同分類的元素互相貢獻的情況，這點需要根據不同的性質與具體情況具體分析。例子有第十三分塊，這裡的連結指向 NOI2020 D1T3。
啟發式思想同樣可以自然地與根號分治相關題目結合，這常用於修改時需要將貢獻合併的情況。我們仍然可以根據貢獻次數分類討論涉及不同部分的修改。具體例子有第四分塊。注意這裡和第二分塊的 trick 並不同質。
詳見這篇部落格。
其實這部分是因為 ynoi 的題十分奇怪沒法好好分類所以單拎出來提一下。
假設我們有一個對 \(n\) 長度序列執行的複雜度為 \(O(n^2)\) 的演演算法，並且這個演演算法處理的資訊支援 \(O(1)\) 合併（例如最大值、加和等）。我們將序列分塊，塊長為 \(\sqrt n\)。對每一塊分別執行此演演算法，單塊複雜度為 \(O(n)\)。總時間複雜度為 \(O(n\sqrt n)\)。
按塊進行可以降低空間複雜度。
例題：[Ynoi2013] D2T2。
加入根號分治和散塊特殊處理的例題：rvrewsus。
有一種樹上資訊，需要每次跳父親得到。我們將樹改成 dfn 序，然後就變成從一個下標跳到另一個下標。同時維護的資訊需要滿足結合律，合併也需要快一些，最好 \(O(1)\)。我們首先分塊，預處理出每個點在塊內跳躍的全資訊，以及其跳出塊的位置。這樣每個塊就可以經過一次資訊合併處理完了。
適用於任意有 \(n-1\) 條關係邊的結構。
stdmxeypz：根號分治 + 平衡思想。
初始化：根號分治，\(\le \sqrt n\) 部分的處理很獨特。
盼君勿忘：根號分治做到 \(O(\sqrt n)\) 維護確定資訊點集下的單次查詢。資訊點集採用莫隊計算。