WaveletTreeによる静的DoubleArrayの圧縮
WaveletTreeを用いるとDoubleArrayが圧縮できるのではないか。ないか、というか、圧縮できる。Bit列に対するrankさえ定数時間で実行できれば、lookupのみ可能なWaveletTreeで良ければ実装できるはず。Bit列に対するrankは、元データの1/5程度の量の補助データがあれば漸近的に定数時間で実行できるそうだ。漸近的に、ってここではどういう意味なのかはよくわからないけど。
WaveletTreeを用いるとDoubleArrayが圧縮できるのではないか。ないか、というか、圧縮できる。Bit列に対するrankさえ定数時間で実行できれば、lookupのみ可能なWaveletTreeで良ければ実装できるはず。Bit列に対するrankは、元データの1/5程度の量の補助データがあれば漸近的に定数時間で実行できるそうだ。漸近的に、ってここではどういう意味なのかはよくわからないけど。