在vp cf的时候遇到的算法，当时看着就是题目很清楚，要不就是我不会的数据结果，要不就是算法，想了一会想不出直接去看题解了。现在补一下。
根号分治虽然名字里面有“分治”但实际上和分治的关系并不大，根号分治更多的还是一种思想。
根号分治的思想是将询问根据一个阈值设为\(S\)分为两部分。两个部分用不同的算法处理，一部分可以用暴力直接处理，另一部分可以通过预处理和动态维护
根号算法是一种优雅的暴力！
涉及到跳多少步的题目一般都是根号分治。
例题
思路：题目等价于让我们求从下标y开始，步长为x的所有数的和
考虑最暴力的暴力对于所有的询问，我们都从y开始跑一遍那么最坏可能会被卡到\(O(nm)\)
然后会发现当m比较大的时候，需要求和的数会很少，我们以\(\sqrt{n}\)为分界线
当步长也就是模数大于\(\sqrt{n}\)最多需要\(O(\sqrt{n})\)的复杂度就可求出
当步长也就是模数小于\(\sqrt{n}\)我们需处理出来需要查询的信息\(O(1)\)去查询
考虑怎么样预处理
\(s[i][j]\)：表示步长为i，起点为j，所有数的和。
枚举起点计算对于每种步长的贡献需要的时间复杂度是\(O(n\sqrt{n})\)
考虑完查询考虑更新
更新的话每次我们需要维护s数组
计算更新当前值对于每种步长的贡献的影响。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
int s[510][510];
void solve()
{
int n,q;cin>>n>>q;
vector<int>a(n+1);
rep(i,1,n){
cin>>a[i];
}
//预处理出来模数比较小的情况
int m=sqrt(n);
rep(i,1,n){
rep(j,1,m){
s[j][i%j]+=a[i];
}
}
while(q--){
char op;cin>>op;
int x,y;cin>>x>>y;
if(op=='A'){
//模数较小直接查询预处理的结果
if(x<=m){
cout<<s[x][y]<<endl;
}else{
//较大的话暴力去做
int ans=0;
for(int i=y;i<=n;i+=x) ans+=a[i];
cout<<ans<<endl;
}
}else{
//改变一个数就需要动态的维护s数组
rep(i,1,m) s[i][x%i]+=y-a[x];
a[x]=y;
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
思路同上面的题目哈希冲突
不过这里m取严格的\(\sqrt(500000)\)会\(t\)
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
int s[800][800];
int a[500010];
void solve()
{
//预处理出来模数比较小的情况
int n=500000,m=sqrt(400000);
int q;cin>>q;
while(q--){
int x,y,op;cin>>op>>x>>y;
if(op==1){
rep(i,1,m) s[i][x%i]+=y;
a[x]+=y;
}else{
if(x<=m){
cout<<s[x][y]<<endl;
}else{
int ans=0;
for(int i=y;i<=n;i+=x){
ans+=a[i];
}
cout<<ans<<endl;
}
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
看到大佬的一句话：要大胆的想，不要因为算法显然太慢，显然有错就放弃对这种算法的思考（因为这通常不会花费太多的时间）
很好的一道题目，dp和根号分治结合的题目
\(f[i][j]\):表示第i个数要加多少次i和j才能>n
考虑转移：
如果\(j\)和\(a[i]\)暴力转移的话会是\(O(n^2)\)的复杂度
考虑根号分治当\(k\)比较大的时候会跳的比较快很快就会大于\(n\)这时我们直接暴力枚举就行
如果\(k\)比较小的话就用dp去进行状态转移，处理出来查询。
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
int s[100010][330];
void solve()
{
int n,q;cin>>n;
vector<int>a(n+1);
rep(i,1,n){
cin>>a[i];
}
//预处理出来模数比较小的情况
int m=sqrt(n);
fep(i,n,1){
rep(j,1,m){
if(i+a[i]+j>n) s[i][j]=1;
else s[i][j]=s[i+a[i]+j][j]+1;
}
}
cin>>q;
while(q--){
int x,y;cin>>x>>y;
//模数较小直接查询预处理的结果
if(y<=m){
cout<<s[x][y]<<endl;
}else{
//较大的话暴力去做
int ans=0;
while(x<=n){
++ans;
x+=a[x]+y;
}
cout<<ans<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
// cin>>_;
// while(_--)
solve();
return 0;
}
这种一次跳几个的一般需要想到根号分治
如果没有前面的那几个系数/权值就是一道比较经典的题目有系数和权值的话需要考虑怎么处理
这里维护两个数组f和g数组
\(f\)数组表示权值前缀和数组但是这里需要每次跳d
\(g\)数组表示单纯前缀和数组
\(f[i][j]=...+\frac{s}{d}a[s]+(\frac{s}{d}+1)a[s+d]+(\frac{s}{d}+2)a[s+2*d]+...\)
\(g[i][j]=...+a[s]+a[s+d]+a[s+2*d]+...\)
我们要求的答案是
$ $
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
int f[330][100010],g[330][100010];
void solve()
{
int n,q;cin>>n>>q;
vector<int>a(n+1);
rep(i,1,n){
cin>>a[i];
}
//预处理出来模数比较小的情况
int sq=sqrt(n);
rep(i,1,sq){
rep(j,1,n){
f[i][j]=(j-i>=0?f[i][j-i]:0)+j/i*a[j];
g[i][j]=(j-i>=0?g[i][j-i]:0)+a[j];
}
}
while(q--){
int s,d,k;cin>>s>>d>>k;
//模数较小直接查询预处理的结果
if(d<=sq){
int ans=0;
ans+=f[d][s+(k-1)*d]-(s-d>=0?f[d][s-d]:0);
ans-=(s/d-1)*(g[d][s+(k-1)*d]-(s-d>=0?g[d][s-d]:0));
cout<<ans<<' ';
}else{
//较大的话暴力去做
int ans=0;
for(int i=s,j=1;j<=k;i+=d,j++){
ans+=j*a[i];
}
cout<<ans<<' ';
}
}
cout<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}