根号分治学习笔记

· · 个人记录

1. 什么是根号分治

如同动态规划，根号分治不是一种算法，是一种思想。

能够根号分治的题目的特征是：

  1. 能够根据某一个值（设为 a）的数据范围，将原问题分为大问题（a\ge B）和小问题（a<B）。
  2. 小问题通常可能的情况不多，可以维护所有可能答案或用离线算法求解，通常时间复杂度为 O(a)。
  3. 大问题可以用暴力求解，通常时间复杂度为 O(n/a)。

此时算法时间复杂度为 O(m\times B+m\times n/B)，当 B=\sqrt{n} 时取得最小值 O(m\sqrt n)。

因此，根号分治本质上是两个针对不同数据规模的暴力。

例：哈希冲突

取 B=\sqrt n，将 x<B 的询问称为小问题，将 x\ge B 的询问称为大问题。

对于小问题，可能的小问题只有 O(B\times B)=O(n) 种，此处采用维护所有可能答案的方法。（带有修改操作，显然不可能离线解决）

维护一个二维数组 b，b(x,y) 表示询问 (x,y) 时的结果。

修改时暴力维护 b 数组，显然修改 (x,y) 时只要将所有 1\le i\le B 将 b(i,x \bmod i) 加上 y-a_i。此部分复杂度 O(m\times B)=O(m\sqrt n)。

对于大问题，注意到当 x\ge B 时，每次询问最多访问 O(n/x)=O(n/B)=O(\sqrt n) 个元素，可以暴力解决，复杂度 O(m\sqrt n)。

习题：Time to Raid Cowavans

提示：

  1. 这题卡空间，不建议使用 O(n^{1.5}) 的空间复杂度。
  2. 这题没有修改操作，可以使用离线算法。

2. 一般分析过程

待更新。

3. 例题选讲

待更新。