根号分治的概念
根号分治是一种优化暴力算法。
我个人的理解就是这东西跟分块差不多。但应用面比分块更广。
其核心思想就是 n n n个数组成的数列，把它分成大于 N \sqrt N N和小于 N \sqrt N N的部分处理。
如果我们能对数据范围进行分块处理，或者两个暴力分别算之后拼接在一起，就用两个合在一起的暴力，实现了正解。
【模板】P3396 哈希冲突
一句话题意：
长度为 n n n 的序列和 m m m 个操作，每次操作有两种类型：
-
询问下标 m o d x mod~~x mod x 后为 y y y 的所有数之和；
-
修改第 x x x 个数；
分析：
这个题的暴力很好打。不再赘述。
cin >> n >> m;
int ans =0;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
for(int i = 1 ; i <= m ; i++){
cin >> cmd >> x >> y;
if(cmd == 'A'){
for(int j = y ; j <= n ; j += x) ans += a[j];
cout << ans << endl;
ans = 0;
}else a[x] = y;
}
这个暴力是 O ( N M ) O(NM) O(NM)的，也就是能通过1e4的数据。
我们再想想怎么优化这个暴力？文章来源：https://www.toymoban.com/news/detail-670091.html
如果 N ≥ N N\ge \sqrt N N≥N文章来源地址https://www.toymoban.com/news/detail-670091.html
到了这里，关于浅谈根号分治——暴力的美学的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
