Mo's algorithmの幅と計算量

Mo's algorithm の区間の幅と計算

区間の個数を$\sqrt{Q}$個や$\sqrt{N}$個にするパターンがあって分からなかったから調べた。

備忘録として書いた。

上の画像のように縦に区切る幅を$W$と設定すると計算量は以下のように求まる

数列の長さを$N$、クエリの個数を$Q$とすると

• ↓↑の移動回数・・・$WQ$
• →の移動回数・・・$\frac{N^2}{W}$

よって合計$\frac{N^2}{W} + WQ$

これを最小にする$W$を求めれば良い。

相加相乗平均の関係より

$$\frac{N^2}{W} + WQ \geqq 2\sqrt{N^2 Q}$$

等号成立は

$$\frac{N^2}{W} = WQ \\ W = \frac{N}{\sqrt{Q}}$$

となる。よって区間の個数は$\sqrt{Q}$個が最適となる。

定数倍を考慮した場合

定数倍を考慮すると$W = \frac{\sqrt{3}N}{\sqrt{2Q}}$となるなしい

参考: https://nyaannyaan.github.io/library/misc/mo.hpp.html