根号分治

根号分治

根号算法——不只是分块。

有时我们会碰到这样一类问题，长度为(n)的序列，(m)个询问（通常(n)和(m)同阶），可能存在两种比较显然的方法，一种是(O(n^2))预处理(O(1))回答，一种是不预处理(O(n))回答(m)个询问，这两种方法都是(O(n^2))的。考虑是否存在一种策略能“平衡”一下预处理和询问的复杂度。

看一道题：哈希冲突。

这是一道论文题，论文的题目就是开头的那句话。先把我们前面提到的两种显然的方法提一下。

第一种(n^2)预处理(f[i][j])表示膜(i)意义下第(j)个hash池内的答案，直接暴力计算，每次修改也是(O(n))的，而且空间复杂度(n^2)。

第二种对于每次询问暴力(O(n))求，修改(O(1))。

这两种方法的复杂度都无法承受，考虑优化。我们发现，对于模数小于(sqrt n)的情况，我们按照第一种方法做，预处理(O(nsqrt n))，空间(O(n))，查询(O(1))；对于模数大于(sqrt n)的情况，模(p)的结果为(i)的hash池中最多只可能有(frac{n}{sqrt n}=sqrt n)个数对它产生贡献，于是采用第二种方法，每次查询复杂度(O(sqrt n))，再加上单次修改(O(sqrt n))。总的复杂度(O((n+m)sqrt n))。

#include<cstdio>
#include<cmath>
#define R register
using namespace std;
const int S=150003,N=403;
int a[S],f[N][N];
int main(){
	R int n,m,p,x,y,i,j,o;
	R char e[2];
	scanf("%d%d",&n,&m),p=sqrt(n);
	for(i=1;i<=n;++i){
		scanf("%d",&a[i]);
		for(j=1;j<=p;++j)
			f[j][i%j]+=a[i];
	}
	for(i=1;i<=m;++i){
		scanf("%s%d%d",e,&x,&y);
		if(e[0]=='A'){
			if(x<=p) printf("%d
",f[x][y]);
			else{
				for(o=0,j=y;j<=n;j+=x)
					o+=a[j];
				printf("%d
",o);
			}
		}
		else{
			for(j=1;j<=p;++j)
				f[j][x%j]+=y-a[x];
			a[x]=y;
		}
	}
	return 0;
}

上面的题目只是牛刀小试，根号分治的应用还有很多，推荐题目：

CF1039D You Are Given a Tree 题解
CF1039E Summer Oenothera Exhibition 题解