簡潔データ構造第2回: ビットベクトルに対する簡潔データ構造 - Retrieva TECH BLOG 簡潔データ構造 - Wikipedia 簡潔ビットベクトル(完備辞書) - Mister雑記 rankとselectが定数時間 この特徴自体は累積和でOK 値域が0/1であることを前提としてコンパクトに保つことができるのが特徴 元の範囲が十分小さければテーブル引きでO(1)になる 8ビットならサイズ256のテーブル 8ビット毎にそこまでの1の数(rank)を記録しておくと、そこまでもO(1)になる このテーブル自体をもう一段圧縮する 例えば512ビットごとにrankを記録しておく 各停・急行・特急の発想