簡潔ビットベクトル

rankとselectが定数時間

値域が0/1であることを前提としてコンパクトに保つことができるのが特徴

元の範囲が十分小さければテーブル引きでO(1)になる

8ビットならサイズ256のテーブル

8ビット毎にそこまでの1の数(rank)を記録しておくと、そこまでもO(1)になる

このテーブル自体をもう一段圧縮する

例えば512ビットごとにrankを記録しておく