# 分塊法
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](/@wiwiho/rJeYetU9S)

先來考慮一個單點修改、區間查詢的問題，然後來個簡單的想法：如果把數列切成好幾塊，然後在修改之後更新那一塊的答案，如果區間查詢的範圍涵蓋一整塊，那麼這一塊的答案就不必重新算，如果有包含到一塊中的一小段，那這段就暴搜，這樣會不會比較好？

數列 $A$ 長度是 $n$，每塊長度是 $k$，那麼分塊會變成類似這樣：

格子中的數字是那一塊的編號，如果數列中的元素是從 $0$ 開始編號的，那麼 $A_i$ 所在的塊編號會是 $\lfloor \frac{i}{k} \rfloor$，總塊數會是 $\lceil \frac{n}{k} \rceil$，注意 $n$ 不一定是 $k$ 的倍數，所以最後會有 $n \bmod k$ 個數字剩下來，它們也算一塊。

在初始化時，計算出每一塊的答案，例如如果查詢求的是區間和，那就儲存每一塊的數字和、求的是最大值，就儲存每一塊裡的最大值。

單點修改的時候，在修改完後，更新那一塊的答案，如果求的答案是區間和，那麼只要把那一塊的和扣掉原來數字，再加上新的數字，這種「可返回」的東西，可以做 $O(1)$ 修改，至於最大、最小值這種「不可返回」的，就把那一塊重新掃一遍，找出最大或最小值，這樣是 $O(k)$ 修改。

區間查詢的時候，如果有完整的一塊被涵蓋，那就直接 $O(1)$ 取那一塊的答案就好，然後暴搜剩下不完整的部分。總塊數有 $\lceil \frac{n}{k} \rceil$ 個，不完整的部分，在查詢區間的左右兩端分別最多 $k - 1$ 個，因此查詢複雜度是 $O(\frac{n}{k}+k)$。

接下來來討論一下 $k$ 應該要取多少好，要讓 $\frac{n}{k}+k$ 盡量小一點，那麼算幾不等式可以派上用場：
$$\frac{\frac{n}{k}+k}{2} \geq \sqrt{\frac{n}{k} \times k}$$

要讓等號成立的話，就必須要 $\frac{n}{k}=k$，解出來可以得到 $k=\sqrt{n}$，這樣查詢和修改複雜度就都是 $O(\sqrt{n})$ 了，如果詢問有 $q$ 筆，再加上預處理的時間，整體複雜度就是 $O(n + q\sqrt{n})$，比暴力破解快了很多。

## 懶人標記

如果要做區間修改的話，用剛剛的方式會變成要對每個單點修改一遍、再去更新每一塊的答案，這樣複雜度是 $O(n)$，太久了。

觀察一下，如果整塊都一起被修改會發生什麼事？
- 如果整塊同時加上 $x$，那麼最大或最小值會加上 $x$，數字和會加上 $x$ 乘上塊大小。
- 如果整塊同時變成 $x$，那麼最大或最小值會變成 $x$，數字和會是 $x$ 乘上塊大小。

由此可知，如果整塊一起變動，那我們可能可以推算出我們想要的答案會如何改變，此時我們就不要浪費時間去修改全部的數字，多開一個變數來儲存這一塊都被改成什麼數字或被多加上多少，這就稱為**懶人標記**。至於邊邊不到一整塊的部分，就一樣暴力處理。

如果某一塊已經有懶人標記，也就是已經被整塊一起修改過，那麼如果之後要再變動這一整塊，只要修改懶人標記就好；但如果之後是只變動部分呢？如果修改是加值的話，硬加上去，不理會懶人標記是可以的，但如果修改是改值，而不理會懶人標記，那麼在查詢時，這個元素的值還是會被覆蓋掉，所以就必須要依懶人標記所記錄的修改，去修改那一塊裡的每一個元素，再去修改剛剛想改的那一部分了。

打一塊的懶人標記是 $O(1)$，塊數最多是 $\frac{n}{k}$，邊邊不到完整一塊的部分，最多就是兩塊，改其中一塊的複雜度是 $O(k)$，因此整體複雜度是 $O(\frac{n}{k}+k)$，把 $k=\sqrt{n}$ 代進去就是 $O(\sqrt{n})$，根本沒變。

## 練習題

- [ZeroJudge d539](https://zerojudge.tw/ShowProblem?problemid=d539) - 區間查詢最大值
- [ZeroJudge d799](https://zerojudge.tw/ShowProblem?problemid=d799) - 區間修改、區間查詢和