ウェーブレット行列による QuantileRange() - アスペ日記

ウェーブレット行列による QuantileRange() - アスペ日記

前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れて...概要を表示 前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れている人には冗長に感じられるかもしれません。 今回は、「配列のある範囲の中にある数字で、n番目に小さい数字を返す」という関数です。 これは少しわかりにくいので、まずウェーブレット行列を使わず、目で数える例を示します。 図の赤線と青線の間にある数字の中で、1番目に小さい数字は何でしょうか。 左から 10個目に 0 があるので、それですね。2番目に小さいものは、左から 17個目と 20個目に 1 があるので、1 です。 では、14番目に小さいものはどれでしょうか。 目で数えてみるとわかりますが、11 です。今回は、それをウェーブレット行列を使って調べる方法を解説します。 図を再掲します。ウェーブレット行列のこの図では、下段が実際に保存しているビット列を表し、上段がそのビットに対応する数字を表します。