根号分治（根号算法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了根号分治（根号算法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

是根号算法，然而不是分块；

是论文，然而不是莫队；

是暴力美学，然而不是暴力。

例题

哈希冲突
$R e main d er P ro b l e m$

~~这两题貌似没有区别~~，我们以 $R e main d er P ro b l e m$ 作为例子来介绍。

题目描述

给你一个长度为 $500000$ 的序列，初值为 $0$ ，你要完成 $q$ 次操作，操作有如下两种：

1 x y : 将下标为 $x$ 的位置的值加上 $y$
2 x y : 询问所有下标模 $x$ 的结果为 $y$ 的位置的值之和

思路

这道题要我们求的，就是以下程序：

for(int i=y;i<=n;i+=x)
    ans+=value[i];

但，这样暴力求解显然超时。

我们发现：

如果 $x$ 很小时，那上面的那层 $f or$ 循环的复杂度更接近 $O (n)$ ；反之，如果 $x$ 很大时，复杂度反而会变小。

这样我们就有了一种思路，

当 $x$ 比较大的时候我们才暴力，如果 $x$ 很小，我们就直接记录答案！！！

这就是 $根号分治$ 的思想，将询问根据数据大小分成两个部分，分别用不同的方法来做。

那分界线是多少呢？

一般规定，是 $\sqrt{n}$ 。

即， $\sqrt{n}$ 时，就暴力求解； $\le \sqrt{n}$ 时，则预处理出答案。

如此，当数据 $\le \sqrt{n}$ 时，每次修改的时间复杂度为为 $O(\sqrt{n})$ ，查询的为 $O (1)$ ；

当数据 $\sqrt{n}$ 时，每次修改的时间复杂度为 $O (1)$ ，查询的为 $O(\sqrt{n})$ 。

通过根号分治，我们就能实现两种操作的时间复杂度均分。

对于预处理，我们用 $f_{i,j}$ 表示所有下标模 $i$ 为 $j$ 的数的和。

$f$ 数组只需开到 $\sqrt{n} * \sqrt{n}$ ，所以空间也不会爆。文章来源地址https://www.toymoban.com/news/detail-841839.html

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,N=5e5,sqrtn=710;
int q;
long long a[maxn],f[sqrtn][sqrtn];
int main(){
	cin>>q;
	int opt,x,y,tmp=sqrt(N);
	while(q--){
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1){ //修改操作 
			for(int i=1;i<=tmp;i++)
				f[i][x%i]+=y;
			a[x]+=y;
		}
		else{ //查询操作 
			if(x<=tmp) printf("%lld\n",f[x][y]);
			else{
				long long ans=0;
				for(int i=y;i<=N;i+=x)
					ans+=a[i];
				printf("%lld\n",ans);
			}
		}
	}
	return 0;
}