ウェーブレット行列を使って、wat-array のクローン（List*Range() を除く）を作ってみました。GitHub リポジトリ: https://github.com/hiroshi-manabe/wavelet-matrix-cppテストは動かない状態です。 wat-array に含まれていた performance_test.cpp を利用…

（注：今回の内容は元論文に書いてあったわけではないので独自研究気味です）前々回と前回で、ウェーブレット行列を使ったアルゴリズムを二つ紹介しました。二つとも、ある配列に対して開始位置と終了位置を指定した範囲についての操作です。RankLessThan(),…

前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れている人には冗長に感じられるかもしれません。今回は、「配列のある範囲の中にある数字で、n番目に小さい数字を返す」という関数です。これは少しわかり…

前回、ウェーブレット木にできることはウェーブレット行列にもできると書きましたが、今回と次回に分けて、ウェーブレット行列を使って2種類の関数を実行する方法を書いてみます。細かく手順を追うため、2進数やビット操作に慣れている人には冗長に感じられ…

ウェーブレット行列のテスト実装に、rank(), select() の他、wat-array で実装されているものをだいたい追加しました。ウェーブレット木でできることは、ウェーブレット行列でも同じようにできる（元論文の最後にちゃんとそう書いてある）ということが確認で…

えちぜんさんによる Wavelet Matrixの紹介記事を読んで、これはすごいと感銘を受けたので、試しに Python で実装してみた。https://github.com/hiroshi-manabe/wavelet-matrix（追記: wat-array を元にした C++版 https://github.com/hiroshi-manabe/wavelet…