前言
- 莫队算法是一种非常经典优雅的
暴力算法
- 而在莫队算法中,最值得探讨的问题自然而然就是:这个块的大小到底应该怎么分?
- 有很多 (OIer) 将它看成一个玄学问题,
非常有道理,但其实我们是能够找到规律的。
普通莫队
- 普通莫队最佳分块大小为 (sqrt n) 。
- 为什么?因为暴力分块的大小为 (sqrt n) ?并不是。
- 那为什么?
- 我们不妨设块的大小为 (s) ,每个块的询问次数为 (q_i) ,序列长度为 (n) ,询问总次数为 (m) 。那么块的总数就是 (frac{n}{s}) ,对于块 (i) 来说,其复杂度为 (q_icdot s+n) 。
- 那么总复杂度为 (sum_{i=1}^{n/s} q_icdot s+n=ms+ncdot frac{n}{s}) 。因为一般 (n) 和 (m) 都是等数量级的,我们可以大致忽略其大小差异,所以总复杂度变为 (ncdot s+n^2cdot frac{1}{s}) 。
- 利用基本不等式可得当 (ncdot s=n^2cdot frac{1}{s}) 即 (s=sqrt n) 时,原式有最小值 (nsqrt n) 。
- 这就是普通莫队算法分块的大小以及时间复杂度的来历。
带修莫队
- 带修莫队最佳分块大小为 (n^{frac{2}{3}}) ,
可惜我不会证明。- 所以我就仅仅
装模作样地分析一番。
-
一开始自学带修莫队的时候有一个疑问,为什么要将右端点也分块?
-
假如右端点不分块,仍然设块的大小为 (s) ,序列长度为 (n) ,询问总次数为 (m) ,修改总次数为 (k) 。那么块的总数还是 (frac{n}{s}) ,此时得到每个块 (i) 的时间复杂度为 (q_icdot s+n+q_icdot k) 。
-
所以总时间复杂度为 (sum_{i=1}^{n/s} q_icdot s+n+q_icdot k=mcdot s+ncdot frac{n}{s}+mcdot k) 。此时我们发现最后面的一项始终为定值,无法通过改变块的大小来改变,所以时间复杂度为 (O(mk)) 。
-
如果分块呢?我们不妨将两个块看成一个整体,表示左右端点在这两个块里的一种情况。每个整体 ((i,j)) 的询问次数为 (q_{ij}) 。但此时整体的总数就不是 (frac{n}{s}) ,而是 (left(frac{n}{s} ight)^2) 了,对于块 ((i,j)) 来说,其复杂度为 (2 imes q_{ij}cdot s+n) 。
-
所以总时间复杂度为 (sum_{i=1}^{(n/s)^2} 2 imes q_{ij}cdot s+n=2 imes mcdot s+ncdot frac{n^2}{s^2}) 。
-
这个时候我们发现每一项都与块的大小 (s) 有关,故可以通过选择一个恰当的块的大小来得到最优的时间复杂度。
-
(Update:(on:2021.3.15)::) 当时可能是脑子抽了……像普通莫队一样直接用基本不等式搞上去就好了。
-
忽略常数并设 (m=n) 可得:(ncdot s+frac{n^3}{s^2}geq sqrt{frac{n^4}{s}}) ,当且仅当 (ncdot s=frac{n^3}{s^2}Rightarrow s=n^{frac{2}{3}}) 时取等。此时 (sqrt{frac{n^4}{s}}=sqrt{n^{frac{10}{3}}}=n^{frac{5}{3}}) 。
证毕。
——2021年2月18日