簡潔ビットベクトルで可能な操作

完備辞書はビットベクトルBに対して以下の操作を提供します¹

${access(B, i)}$ : B[i]を返す
${rank_b(B, i)}$ : B[1, i]のbの数を返す
${select_b(B, i)}$ : Bの先頭からi番目のbの位置を返す

index	1	2	3	4	5	6	7	8
B	1	1	0	0	1	1	1	0

${access(B, 1) = 1}$
${rank_0(B, 5) = 2}$
${rank_1(B, 5) = 3}$
${select_0(B, 3) = 8}$
${select_1(B, 3) = 5}$

rank

索引の構築

rankを定数時間で実行するために，索引として大ブロックL，小ブロックS，テーブルPを作成します．

大ブロックLには，長さlごとに直前までに現れた1の総数を記録します．
小ブロックSには，長さsごとに直前までに現れた1の総数を記録します．その際，メモリ節約のため所属する大ブロックに記録した数との差分を記録するようにします．
テーブルPには，長さsのすべてのbitパターンとそのrankの値を記録します．

lを16，sを8としたときは以下のようになります．

f:id:MitI_7:20180415155140p:plain

索引の空間計算量

ビットベクトルの長さがnのとき各索引のサイズは下のようになります．
大ブロックL： ${(n / l) \cdot lg \,n}$ ビット
小ブロックS： ${(n / s) \cdot lg \, l}$ ビット
テーブルP： ${2^s \cdot lg \, s}$ ビット

小ブロックは大ブロックからの差分を記録するため，ひとつのブロックは ${lg \, l}$ ビットとなります．ここでlを ${lg^2 \, n}$ ，sを ${(1 / 2) lg \, n}$ とすると，合計サイズをn + o(n)ビットに抑えることができます．

rank操作

${rank_1(B, i)}$ を求めるには，iの所属する大ブロックLの値，iの所属する小ブロックSの値，小ブロックの位置からiまでの1の数を足し合わせる必要があります．
大ブロックの位置xは ${\lceil i / l \rceil}$ ，小ブロックの位置yは ${\lceil i / s \rceil}$ ，テーブルPのパターンpはB[s(y - 1) + 1, i]となります²．
よってrankは以下のように求めることができます．
$\displaystyle rank_1(B, i) = L[x] + S[y] + P[p]$

以上のすべての操作は定数時間で可能なため，rankは定数時間で計算できます．また， ${rank_0(B, i) = i - rank_1(B, i) }$ という関係があるため ${rank_0(B, i)}$ も定数時間で計算することができます．

具体例として，lを16，sを8としたときの ${rank_1(B, 29)}$ を求めてみます．
大ブロックの位置xは ${\lceil 29 / 16 \rceil}$ なので2となります．
小ブロックの位置yは ${\lceil 29 / 8 \rceil}$ なので4となります．
テーブルPのパターンpは ${B[ 8 \cdot (4 - 1) + 1, 29 ] }$ なので[1, 1, 1, 0, 1]となります．
以上のことから ${rank_1(B, 28) = L[2] + S[4] + P[11101000] = 10 + 4 + 4 = 18}$ と求めることができました．

f:id:MitI_7:20180414142543p:plain

select

select操作

selectはrankよりも複雑なので，select用の索引は作らずにrank用の索引を2分探索して求めることが多いみたいです．rank自体は定数時間で求められるのでこの操作はO(lg n)で実行可能です．
${select_b(B, j)}$ を求めるには， ${rank_b(B, i) = j}$ かつ ${rank_b(B, i - 1) = j - 1}$ となるようなiを見つければいいです．
このとき，ビットベクトルBを直接探索するのではなく，大ブロックLと小ブロックSと順に2分探索することで高速化が可能です．
まず ${ L[p] \lt j }$ となるような最大のpを大ブロックLを2分探索して見つけます．
つぎに ${L[p] + S[q] \lt j }$ となるような最大のqを小ブロックSを2分探索して見つけます．
ここでiはq番目の小ブロックに所属していることがわかるので，あとは ${ B[s(q - 1) + 1, s \cdot q ] }$ を辞書引きするか前から探索するかして求めることができます．

ソース

github.com

参考

今回はすべて1-originの閉区間を考えます↩
${\lceil \, \rceil}$ は天井関数↩