順列の簡潔データ構造 - くじらにっき++

助教の先生と @yurahuna で簡潔データ構造の輪講をやっています。今週は順列のところを担当したのですが，とてもトリッキーで楽しいデータ構造だと思ったので一部を公開しておきます。これまでの章の内容（定数時間の rank, succ, pred を実現する Bitvector など）に対して依存関係が生じている件は申し訳ありません…

speakerdeck.com

読み進めているのは以下の本です。1章は簡潔データ構造の意義や計算量の解析に必要な数学について，2章はエントロピーと符号化について，3章以降はArrays, Bitvectors, Permutations, Sequences, Parentheses, Trees, … のように続きます。