takeda25 https://blog.hatena.ne.jp/takeda25/ アスペ日記 https://takeda25.hatenablog.jp/ アルゴリズム ウェーブレット行列 前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れている人には冗長に感じられるかもしれません。今回は、「配列のある範囲の中にある数字で、n番目に小さい数字を返す」という関数です。これは少しわかりにくいので、まずウェーブレット行列を使わず、目で数える例を示します。 図の赤線と青線の間にある数字の中で、1番目に小さい数字は何でしょうか。左から 10個目に 0 があるので、それですね。2番目に小さいものは、左から 17個目と 20個目に 1 があるので、1 です。では、14番目に小さいものはどれでしょうか。目で数えてみるとわかりますが、11 です。今回は… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakeda25.hatenablog.jp%2Fentry%2F20120807%2F1344306670" title="ウェーブレット行列による QuantileRange() - アスペ日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/t/takeda25/20120807/20120807111106.png Hatena Blog https://hatena.blog 2012-08-07 11:31:10 rich https://takeda25.hatenablog.jp/entry/20120807/1344306670 1.0 100%