rank/select の実装

rank/select の実装を探していて、Sux4J というライブラリがあった。

Sux: Implementing Succinct Data Structures
http://sux.di.unimi.it/

参考までに sux4j-3.0.4-sources.jar のソースをちょっと読んだんだけど、it.unimi.dsi.sux4j.bits.Rank16 の59行目の計算間違いでメモリを余分に確保しているような気が…。

僕の気のせいかもしれないので、そっとしておこう。