分塊法

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

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

格子中的數字是那一塊的編號，如果數列中的元素是從 開始編號的，那麼 所在的塊編號會是 ，總塊數會是 ，注意 不一定是 的倍數，所以最後會有 個數字剩下來，它們也算一塊。

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

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

區間查詢的時候，如果有完整的一塊被涵蓋，那就直接 取那一塊的答案就好，然後暴搜剩下不完整的部分。總塊數有 個，不完整的部分，在查詢區間的左右兩端分別最多 個，因此查詢複雜度是 。

接下來來討論一下 應該要取多少好，要讓 盡量小一點，那麼算幾不等式可以派上用場：

要讓等號成立的話，就必須要 ，解出來可以得到 ，這樣查詢和修改複雜度就都是 了，如果詢問有 筆，再加上預處理的時間，整體複雜度就是 ，比暴力破解快了很多。

懶人標記

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

觀察一下，如果整塊都一起被修改會發生什麼事？

• 如果整塊同時加上 ，那麼最大或最小值會加上 ，數字和會加上 乘上塊大小。
• 如果整塊同時變成 ，那麼最大或最小值會變成 ，數字和會是 乘上塊大小。

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

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

打一塊的懶人標記是 ，塊數最多是 ，邊邊不到完整一塊的部分，最多就是兩塊，改其中一塊的複雜度是 ，因此整體複雜度是 ，把 代進去就是 ，根本沒變。

練習題

• ZeroJudge d539 - 區間查詢最大值
• ZeroJudge d799 - 區間修改、區間查詢和