首页 > 其他分享 >根号分治

根号分治

时间:2023-01-07 10:34:36浏览次数:44  
标签:质数 分治 sqrt 数据 复杂度 根号

概述

  • 根号分治,是一种对数据进行分治的分治方式。

  • 具体来说,如果所要求进行的过程满足如下性质:

    1. 根号以下的数据的种类很少,可以全部维护之;

    2. 根号以上的数据,直接暴力的复杂度可接受。

  • 那么可以考虑使用根号分治。

  • 通常根号分治往往和数论上的小质数、大质数(以根号为界)的性质相关,例如 func 那道题,故也许也可以叫数论分治。

  • 一定程度上,根号分治也是一种数据分治,只不过不是数据点分治罢了(笑)。

P3396 哈希冲突

  • 题意:给定序列 \(a_{1\sim n}\),有 \(m\) 个操作,为单点修改或求 \(\sum\limits_{i\bmod p=x} a_i\)。

  • 数据范围:\(n,m\leqslant 1.5\times 10^5,p<n\)。

  • 注意到传统方法,譬如线段树和分块,都不能很好地处理 \(\bmod p=x\) 的和,究其原因是 \(p\) 太多了,不同的 \(p\) 之间又互相难以复用。

  • 但观察到对于大数即 \(\geqslant \sqrt{n}\) 的 \(p\),直接暴力的复杂度是 \(O(n\sqrt{n})\)。

  • 于是考虑根号分治,小数只有 \(O(\sqrt{n})\) 个,修改时直接暴力修改。

  • 总复杂度 \(O(\sqrt{n})\)。

标签:质数,分治,sqrt,数据,复杂度,根号
From: https://www.cnblogs.com/weixin2024/p/17032201.html

相关文章