前言

如題。

值域分塊

顧名思義，就是在桶上分塊。

它的用處是把區間修改和區間詢問中某一種操作變成 \(O(1)\)，另一種變成 \(O(\sqrt n)\)。

所以經常用來輔助維護兩種操作數量嚴重不對等的數據結構。

典型代表有莫隊和根號分治。

這里看一個莫隊的例子。

如我們要維護一個二維數點。

那么莫隊上的操作就是 \(O(n \sqrt n)\) 次單點加和 \(O(n)\) 次區間求和。

那么單點加時維護所屬塊的總和，就可以在區間查詢時加速對于整塊的查詢而做到 \(O(\sqrt n)\) 查詢。

具體代碼如下：

void Add(int x){
	int bl=x/sq+1;
	if(x%sq==0){
		bl--;
	}
	cnt[x]++;
	block[bl]++;
}
void Del(int x){
	int bl=x/sq+1;
    if(x%sq==0){
		bl--;
	}
	cnt[x]--;
	block[bl]--;
}
int query(int x){
    int res=0;
	for(int i=0;i<=400;i++){
		if((i-1)*sq+1<=x&&x<=i*sq){
			for(int j=(i-1)*sq+1;j<=i*sq;j++){
                res+=cnt[j];
				if(j==x){
					return res;
				}
			}
		}
        res+=block[i];
	}
    return res;
}

根號重構

這個方法是用來維護諸如翻轉之類的區間操作的。

首先你需要把所有點縮到一個塊里。

然后對于每次操作，把操作兩個端點從其所屬塊中斷開（類似于珂朵莉樹的搞法）。

然后這個問題就變成了整塊下的問題。

那么現在就可以暴力去搞了。

但是注意到塊很多的時候時間會退化到 \(O(n^2)\)。

所以當塊的數量多余 \(\sqrt n\) 時，暴力重構所有塊。

具體來說把所有塊再次縮到一個塊中。

這樣保證了操作復雜度不會高于 \(O(\sqrt n)\)。

另外由于每次只會增加常數個塊，所以重構數量是 \(O(\sqrt n)\) 的。

那么總復雜度也就只有 \(O(n \sqrt n)\)。

莫隊二離