---
tags: 進階資料結構
title: 分塊法
---

# 分塊法

:::info
### 題目在這裡～
- [loj 6227](https://loj.ac/p/6277)
- [zerojudge b417](https://zerojudge.tw/ShowProblem?problemid=b417)
- [CF 617E](https://codeforces.com/problemset/problem/617/E)
- [CF 877F](https://codeforces.com/problemset/problem/877/F)
:::

:::success
## 分塊思想

- 使用條件：區間相關操作
- 如果覺得線段樹太難寫，或是常數太大，亦或是空間使用太多，快來考慮這方法～

### 正式開始
- 我們拿區間max為例子（不帶修改），考慮序列長度為 $N$
- 把陣列分成 $B$ 塊，每一塊大小為 $K = \lceil{\frac{N}{B}}\rceil$ （大約就是 $\frac{N}{B}$ ）
- **對於每塊儲存該塊元素中最大值**
- 這樣對於區間查詢，最多完全包含 $B-2$ 個塊，不包含在快中的元素最多 $2 \times (K-1)$ 個
- 於是乎：
- 單次查詢時間：$O(B+K) = O(B+\frac{N}{B}) >= O(\sqrt{N})$
- 此時 $B ≒ \sqrt{N}$

<br>

*覺得學這沒用嗎？下面我們講講**莫隊***
:::

:::success
## 普通莫隊算法
- 這邊拿區間眾數來舉例子（不帶修改）
- 把陣列分成 $B$ 塊，每一塊大小為 $K = \lceil{\frac{N}{B}}\rceil$ （大約就是 $\frac{N}{B}$ ）
- 我們想把所有查詢照著某個順序排序之後再處理，此技巧為**離線算法**
- 同時維護目前的區間需要的資訊（當然包括答案），並且透過移動左右指針去尋找每一個詢問的答案
- 舉個簡單的例子：
- 我們有詢問區間 $[5,6],[2,6],[1,2],[1,4]$
- 照著左端排序後變成 $[1,2],[1,4],[2,6],[5,6]$
- 一開始兩指針 $L=1,R=1$
- 我們開始做操作：
- $R$ 往右 1 次 -> $[1,2]$
- $R$ 往右 2 次 -> $[1,4]$
- $L$ 往右 1 次，$R$ 往右 2 次 -> $[2,6]$
- $L$ 往右 3 次 -> $[5,6]$
- 當然，通常不太可能所有操作都這麼漂亮的只往右移動。如果需要往左移動，時間就得花比較久
- 我們定義排序的方法：
- 兩個詢問以 $[l_i, r_i], [l_j, r_j]$ 表示
- 當 $l_i, l_j$ 在不同區塊時，$l$ 較小的排前面
- 當 $l_i, l_j$ 在同一區塊時，$r$ 較小的排前面
- 同樣的透過移動左右指針去尋找每一個詢問的答案，我們來算時間複雜度：（有 $Q$ 個詢問）
- 左（ $L$ ）指針移動：
- 塊內移動距離最多為 $K-1$
- 移到下一塊的距離最多 $2\times K-1$
- 總時間為 $O(QK)$
- 右（ $R$ ）指針移動：
- 當 $l$ 在同一塊時總往右移動距離最多為 $N-1$ （$\times B$）
- 當 $l$ 往下一塊時往左移動距離最多為 $N-1$（$\times (B-1)$）
- 總時間為 $O(NB)$
- 加起來：
- $O(QK + NB) = O(\frac{QN}{B}+NB) >= O(N\sqrt{Q})$
- 因此
- 時間複雜度：$O(N\sqrt{Q})$
- 此時 $B = \sqrt{Q}, K = \frac{N}{\sqrt{Q}}$
:::

:::success
## 帶修改莫隊
- 這個
:::

:::success
## 實驗室
https://codeforces.com/contest/1509/problem/0
(●'◡'●)⁅⁆‹›⁽⁾¦-«»©®℗™'‘’‚‛¬÷–“”„‟⁄¤؋৻฿₡₤₧₧₥₨₢૱៛৲¥¢£֏৳৳௹₠₣₦₩₿₼₹₳₶₰₭₪₫₮₱₴₷₺﷼₽₸⇳⇷⇸⇿■▦≣≗≘≡≧≤≪≭⊃⊄︿︷﹀⺐⺓⺨⺔⺨⺔ㄊ⨊⨇⨈⨌⨉⨆⨈⨋⨎⨑⨗⨔⨭⨮⨫‱※⁜♪±⁋⁊ª‽ʬʭ□■¾⅕⅔½¼⅓⅖∝∑
:::