Wavelet Matrix 3D [2]

前回の実装を簡略化する。

実装方法

Wavelet Matrix の性質を利用すれば、2 次元から 3 次元へは自然に拡張することができる。

Wavelet Matrix 用のビットベクトルを $O(\log{Y} \log{Z})$ 個用意し、$O(\log{Y} \log{Z})$ 個のセパレータを用意するだけで大丈夫。これで、

  • 構築時間: $O(X \log{Y} \log{Z})$
  • 領域: $O(X \log{Y} \log{Z} / W)$($W$ は 32 や 64)
  • クエリ: $O(\log{Y}\log{Z})$

にできる。

キャッシュ効率はやや悪化してしまうが、実装はとても軽くなる。

追加メモリ使用量は、ほぼ $X (24 + (\lfloor{\log_2{Y}\rfloor} + 2)(\lfloor{\log_2{Z}\rfloor} + 1) / 4)$ Bytes で、

  • $N = 10^5$ で 10.4 MB
  • $N = 10^6$ で 133 MB
  • $N = 5 \cdot 10^6$ で 830 MB

ほどになる($N = X = Y = Z$ とする)。

実行時間とソースコード


その他

  • anta さんの WaveletMatrix のライブラリ中の WaveletMatrixPower で既出だった。