Bit Vector

個人的メモ

ここでいう bit vector とは長さ $n$ のビット列を簡潔(空間計算量 $n + o(n)$ ビット) にかつ rank($i$ ビット以下に $1$ がいくつあるか) select($i$ 番目の $1$ は何 ビット目にあるか) を高速に処理することのできるデータ構造のことである.
このスライド を参考に理論自体は理解できたが, 実装を行う上でいくつかの問題が生じた.
rank はある程度省メモリで $\O (1)$ time で処理できるが select の方で少々問題が生じる. select では全体を $\lceil \log^2 n \rceil$ 個の $1$ を持つ block に分ける. このとき block のサイズが $\log^c n$ ($c$ はある定数) 以下の小さいものについては $\sqrt {\log n}$ 分木を構築して効率よく処理する.
この際に木の親から子へ $\O (1)$ でたどれるようにするために表引きを持っておく必要があり, 木のすべての子についての情報は $\sqrt{\log n} \times 2 \log \log n = \O (\log n)$ bit で表される(子の数 $\times$ $\log$ ($1$ の数)) から $2^{\sqrt {\log n} \times 2 \log \log n} = \O (n(\log \log n / \log n))$ bit で表引きが持てると書かれている.
漸近的には $2^{\sqrt{\log n} \times 2 \log \log n} = \mathrm{o}(n)$ かも知れないが実際には全体の bit の長さを $10^6$ とかと考えると $2^{50}$ 近くになり到底持てない. 実用上は情報をたとえば $1/3$ とか $1/4$ とかに定数分割して表引きを構築するらしい(研究している人談) のだがなかなかに泥沼な実装になりそうだったので親から子にたどる部分には二分探索を用いて $\O( \log \log n)$ time での実装をした.
結論としてはまず値に応じたビット長を確保するのが厳しいし, また select $\O (1)$ time 実装は険しい&ちゃんと実装しないとそんなに速くならないだろうという感じ.