根号分治
将一组询问按照某个值域来划分（通常取根号）不超过 \(x\) 时一种做法，超过 \(x\) 另一种做法
例题1（P3396 哈希冲突）
for(int i=y;i<=n;i+=x)
这是暴力算法的单次操作，不难看出当 \(x\) 足够大时暴力并不慢，当 \(x>=sqrt(n)\) 时，时间复杂度为 \(O(sqrt(n))\) ,当 \(x<=sqrt\) 时，我们可以 \(O(n * sqrt(n))\) 预处理 \(O(1)\) 回答,修改单个 \(x<=sqrt(n)\) 的值只需要 \(O(sqrt(n))\) ,总时间复杂度为 \(O(m * sqrt(n))\) 级别
正解：
#include<bits/stdc++.h>
using namespace std;
int a[150005];
int n,m,x,y;
long long dp[400][400];
char C;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){//输入
cin>>a[i];
}
for(int i=1;i<=n;i++)//预处理x<=sqrt(n)的答案
for(int j=1;j<=sqrt(n);j++)
dp[j][i%j]+=a[i];
while(m--){
cin>>C;
cin>>x>>y;
if(C!='A'){
for(int i=1;i<=sqrt(n);i++)//修改单个值把每一次旧的计数换成新的
dp[i][x%i]+=y-a[x];
a[x]=y;
}
else{
if(x<=sqrt(n)) cout<<dp[x][y]<<endl;
else{
long long ans=0;
for(int i=y;i<=n;i+=x) ans+=a[i];//x>sqrt(n)
cout<<ans<<endl;
}
}
}
return 0;
}
例题2（CF103D Time to Raid Cowavans）
1.将公差k按根号分治，暴力枚举，单次时间复杂度 \(O(sqrt(n))\)
2.设 \(dp[i][j]\) 表示首项为 \(i\) ，公差为 \(j\) 的区间和
3.离线数据，将公差排序，公差相同的一起计算
\(ps\) :你可能会对为什么要离线感到不解，写一下就会发现 \(k<=sqrt(n)\) 的部分按上一题的方式写两维需要 \(3e5 * 500\) 的空间 \((sqrt(n)<500)\) ，显然 \(MLE\) ，考虑我们不能把所有 \(k<=sqrt(n)\) 的答案记录下来，但是当 \(k\) 确定时只用枚举起点，存得下，所以离线所有的询问, \(k\) 值相同的可以一起处理，每次更新先在存储的 \(k\) 值也很快（后缀数组 \(O(n)\) ）,注意一个细节：后缀数组计算起点为 \(n\) 的结果会调用 \(n+k(k<500)\) 的结果，所以数组要开大 500
正解：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,k;
int m,n;
int a[310000];
int dp[310000];
int rec[310000];
struct que{
int id;
int t;
int k;
}q[310000];
bool cmp(que a,que b){
return a.k<b.k;
}
void help(int kk){
for(int i=0;i<=309999;i++) dp[i]=0;
for(int i=n;i>=1;i--){
dp[i]=dp[i+kk]+a[i];
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>t>>k;
q[i].t=t;
q[i].k=k;
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;i++){
if(q[i].k!=q[i-1].k && q[i].k<=500){
help(q[i].k);
}
if(q[i].k<=500 && q[i].t<=n){
rec[q[i].id]=dp[q[i].t];
}
else{
for(int j=q[i].t;j<=n;j+=q[i].k){
rec[q[i].id]+=a[j];
}
}
}
for(int i=1;i<=m;i++){
cout<<rec[i]<<endl;
}
return 0;
}
例题3（CF1580C Train Maintenance)
1.一辆车就是一个周期 \(x[i]+y[i]\)
2.以 \(sqrt(m)\) 为界，当周期超过段数时，则段数
不超过 \(sqrt(m)\) ，暴力枚举，区间修改（差分，线段树，分块）
3.若周期不超过 \(sqrt(m)\) ，则周期的种类也不超过 \(sqrt(m)\) , \(dp[i][j]\) 表示周期为 \(i\) 的列车在模 \(i\) 余数为 \(j\) 天的维修的车数
对于第 \(k\) 种车，周期 \(i=x[k]+y[k]\) ，将其贡献添加到 \(dp[i][j]\) 中去
#include<bits/stdc++.h>
using namespace std;
int x[200005],y[200005];
int tim[200005],cnt[3005][3005];
int n,m,c[200005];
void add(int x,int s){
if(x>m)return;
c[x]+=s;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
//lkhjlkhl
int S=min(m+0.0,sqrt(m+0.5)),lst=0;
for(int l=1;l<=m;l++){
int op,k;
cin>>op>>k;
//dsgsdfhsdrysdh
int aa=3-2*op;
if(op==1)tim[k]=l;
if(x[k]+y[k]>S){
for(int i=tim[k]+x[k];i<=m;i+=x[k]+y[k])
add(max(i,l),aa),add(max(l,i+y[k]),-aa);
}
else{
for(int i=tim[k]+x[k];i<tim[k]+x[k]+y[k];i++)
cnt[x[k]+y[k]][i%(x[k]+y[k])]+=aa;
}
//hjfnhbfvbn
int ans=lst+c[l];
lst=ans;
for(int i=1;i<=S;i++)ans+=cnt[i][l%i];
printf("%d\n",ans);
}
//pouiudjh
return 0;
}