Implementation of Range Min-Max Tree

前に論文を読んで放置していた、簡潔木構造の1バージョンであるrange min-max treeを実装した。

https://github.com/LennMars/SuccinctTrees

基本的な仕組みは
K. Sadakane and G. Navarro. Fully-functional succinct trees. In Proc. 21st SODA, pages 134–149, 2010.
パラメータ設定は
D. Arroyuelo, R. C ́novas, G. Navarro and K. Sadakane. Succinct trees in practice. In Proc. ALENEX, pages 84–97, 2010.
を参照した。

現論文に"easily implemented"とあるように300行程度の簡潔な実装で、特に真面目な最適化はしていない。どのような入力に対してどれくらいの性能が求められるのかいまいち勘所がよく分からないが、単純なクエリにおいては2番目の論文に載っているのとだいたい同程度の性能が出ているように見える。