完備辞書実装したという記事書きましたが、そもそもウェーブレット行列実装するために実装したのでした。忘れてました…

ウェーブレット行列とは

ここに書いてあります。

簡単に言うと「完備辞書を使って、数字のみの配列に対しrank()とselect()を行う」データ構造です。数字のみと言いましたが、文字列でも数字に変換できればウェーブレット行列で扱えます。

実装したもの

こちらになります。new WM(array) とするとウェーブレット行列を作ることができます。

rank()では2つ引数を取ります。rank()は「(一つ目の引数) 番目までの (ふたつ目の引数) の個数」を返します。例えば rank(37, 11) ならば37番目までの11の個数を返します。

select()も実装しました。まあ実は定数時間ではなくて対数時間になってます。O(n)よりは早いから許してください。

どうや色々なことができると聞いたので試しに幾つか実装しました。

quantile(s, e, k): [s, e)の範囲でk番目の値を返します。
rangemax(s, e): [s, e)の範囲で最大の値を返します。実はkを指定するとk番目まで大きい順に返すという仕様なのですが、うまく実装できませんでした…