ウェーブレット行列による QuantileRange()
前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れている人には冗長に感じられるかもしれません。
今回は、「配列のある範囲の中にある数字で、n番目に小さい数字を返す」という関数です。
これは少しわかりにくいので、まずウェーブレット行列を使わず、目で数える例を示します。
図の赤線と青線の間にある数字の中で、1番目に小さい数字は何でしょうか。
左から 10個目に 0 があるので、それですね。2番目に小さいものは、左から 17個目と 20個目に 1 があるので、1 です。
では、14番目に小さいものはどれでしょうか。
目で数えてみるとわかりますが、11 です。今回は、それをウェーブレット行列を使って調べる方法を解説します。
図を再掲します。ウェーブレット行列のこの図では、下段が実際に保存しているビット列を表し、上段がそのビットに対応する数字を表します。上段の数字は保存されていません。検索範囲は、インデックス 5 から 25 です。
最初のレベルでは、ビット列は各数字の最上位ビットを表しています。
まず、赤線と青線の間で、最上位ビットが "0" であるものの数えます。なぜ数えるかということは、一旦置いておきます。
「ある位置より左にある "0" または "1" の数を数える」ということは簡潔ビットベクトルというデータ構造を使うと定数時間でできるため、それを利用します。すると、範囲内の "0" の数え方は、「青線の左にある "0" の数から、赤線の左にある "0" の数を引く」というやり方になります。その答えは 11個です。
範囲内に、最上位ビットが "0" のものは 11個あるということになります。そして、最上位ビットが "1" のものは、残りの 9個です（範囲全体の大きさは 20個なので）。
さて、「14番目に小さい数字」は、最上位ビットが "0" のものと "1" のもののどちらに属するでしょうか。
答えは、「最上位ビットが "1" のもの」です。
ちょっと考えてみます。最上位ビットが "0" のものと、最上位ビットが "1" のものでは、どちらが大きいでしょうか。もちろん、"1" のものですね。なので、最上位ビットが "0" のものが 11個あるということは、1番目から 11番目に小さい数字は最上位ビットが "0" で、12番目から 20番目に小さい数字は最上位ビットが "1" ということになります。つまり、今探している 14番目に小さい数字は、最上位ビットが "1" のグループに入ります。
最上位ビットが "1" とわかったので、次のレベルでは、最上位ビットが "1" であるものの中から調べることになります。
次のレベルでの検索範囲を調べるため、赤線と青線のそれぞれ左にある "1" の数を考えます。この時、それぞれの線の左にある "0" の数をすでに数えてあるため、改めて "1" の数を数える必要はありません。赤線の位置は 5 とわかっているので、"0" が左に 3個あるということは、"1" が左に 2個あるということです。同じく青線についても、位置は 25 で、左にある "0" の数が 14 個なので、左にある "1" の数は 11個ということになります。
つまり、次のレベルでは、赤線は中央の「0-1境界線」から右に 2 の位置、青線は右に 11 の位置になります。図を示します。
ところで、このレベルでは、検索範囲の中で最上位ビットが "1" のものだけが残っています。最上位ビットが "0" のものは、小さいとわかっているので排除したことになります。その数は、上のレベルと今のレベルの範囲の差、つまり 11個です。
探したいものは「14番目に小さい数字」なのですが、小さいものを 11個排除したので、ここからは「3番目に小さい数字」を探すことになります。
さて、このレベルでも同じように "0" の数を数えます。答えは 3個です。つまり、1番目から 3番目に小さい数字は、2番目のビットが "0" ということです。
ということは、次のレベルでは、上から 2番目のビットが "0" であるものに絞って検索することになります。赤線と青線について、それぞれ左にある "0" の数は 8個と 11個なので、次のレベルでの検索範囲は下の図のようになります。
2レベル目では、対象ビットが "0" だったため、小さいものを排除するということはしていません。なので、「3番目に小さい数字」という条件は変わりません。
今回、"0" はひとつもありません。ということは、「3番目に小さい数字」の 上から 3番目のビットは "1" ということになります。
また範囲を計算します。赤線と青線の左にある "1" の数はそれぞれ 3個と 6個なので、中央の「0-1境界線」からそれぞれ右に 3 と 6 の位置になります。
範囲内の "0"の数は 1個なので、1番目に小さい数だけ、上から 4番目（一番下）のビットが "0" ということになります。探しているのは 3番目に小さい数なので、一番下のビットが "1" ということになります。
これで、探している数字のビットはすべてわかりました。最上位ビットが "1"、上から 2番目が "0"、3番目が "1"、4番目が "1" なので、答えは 1011、つまり 10進数で 11 になります。
ですが、元々の範囲内を見ると、11 は複数あります。どの 11 を答えとするかについて、もう少し考えてみます。
最後のレベルで調べているのは、「3番目に小さい数字」でしたが、一番下のビットが "0" のものを 1つ排除したので、今では「2番目に小さい数字」ということになります。ここで、最後のレベルからもうひとつ下のレベルを考えると、範囲は次の図のようになります。
「2番目に小さい」ということは、左の位置を小さいとすると、右のほうの 11 ということになります。それは、11 全体でいうと 3番目のものということになります。つまり、「左から 3番目の 11」、元の配列でインデックス 17 の位置ということになります。これは、Select() で求められます。もっとも、Select() にもコストがかかるので、返値としては「3番目の 11」という情報を返したほうが、呼び出し側でその位置を求めるかどうかが選択できていいかもしれません。
