ウェーブレット行列による RankLessThan()

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

まず、「配列のある範囲と、ある数字を与えて、範囲内でその数字が出てくる回数・それより小さいものが出てくる回数・それより大きいものが出てくる回数を返す」という関数です。

例として、前回のウェーブレット行列を使います。範囲はインデックス 8から 24（最後のもの（24）は含まない。以下同じ）で、キーの数字を "6" とします。

今回、ウェーブレット行列の 1レベル目（最上位ビットに対応）を次のように表します。実際に持っているのは下段のビット列のみで、上段の数字は元配列でそれぞれに対応する数字です。8から 24という範囲は、図の赤線から青線の間です。

この範囲の中に、最上位ビットが "0" のものと "1" のものが混じっています。ところで、キーの数字は "6"（2進数で 0110）なので、最上位ビットは "0" です。すると、範囲内の数字で最上位ビットが "0" のものと "1" のもののそれぞれについて、どのようなことが言えるでしょうか。

答えは、次のようになります。

最上位ビットが "0" のもの: "6" より小さい（3, 5 など）、"6" そのもの、"6" より大きい（7）
最上位ビットが "1" のもの: "6" より大きい（10, 13, 14 など）

つまり、最上位ビットが "0" のものについては、"6" との大小関係は不明なままですが、"1" のものは確実に "6" より大きいということが言えます。なので、最上位ビットが "1" のものについては、「"6" より大きいもの」としてカウントします。

その数をどうやって求めるか。その前に、次のレベルで検索範囲がどうなるかを考えます。

"6" の最上位ビットは "0" なので、次のレベルでは、最上位ビットが "0" のものを集めた「左半分」に絞って検索することになります。今のレベルで、検索範囲の始まりである赤線から左にある "0" の数を数えると 0, 6, 5, 2, 7 に対応する 5個なので、次のレベルでは赤線の位置は 5 になります。また、青線の左にある "0"の数は 14個なので、次のレベル（2レベル目）での青線の位置は 14 になります。

つまり、2レベル目での検索範囲は、次のようになります。黒線は、最上位ビットが "0" のものと "1" のものとの境界です。

ところで、1レベル目の範囲内で最上位ビットが "1" だったものの数ですが、「1レベル目での範囲の大きさ-2レベル目での範囲の大きさ」になります。というのは、1レベル目の範囲からキーの数字とビットが合わないものを排除した結果が今回の範囲なので、排除したもの、つまり最上位ビットが "1" のものの数は、それらの差分になるということです。今回の範囲の大きさは 9なので、1レベル目の範囲との差分は 16-9=7 個で、これが「キーである "6" よりも大きいと確定したもの」の数になります。

さて、今度のレベルは、上から 2ビット目に対応することになります。キーである "6"（2進数で 0110）は、そのビットが立っています。そして、検索範囲の中にある数字はすべて最上位ビットがキーである "6" と同じなので、次のことが言えます。

上から 2ビット目が "0" のもの: "6" より小さい（0, 1, 2, 3）
上から 2ビット目が "1" のもの: "6" より小さい、"6" そのもの、"6" より大きい

つまり今回は、上から 2ビット目が "0" のものについては "6" より小さいと確定でき、"1" のものについては不明ということです。

今回も、次の検索位置を決めます。今回、キーである "6" は上から 2ビット目が "1" なので、"1" に注目します。赤線の左にある "1" の数は 3個で、青線の左にある "1" の数は 8個です。つまり、次のレベル（3レベル目）での検索位置は、このレベルでビットが "1" だったものの中で 3番目から 8番目ということになります。

3レベル目での検索範囲は、次のようになります。黒い太線が、2ビット目が "0" のものと "1" のものの境界なので、そこから 3つ右が開始位置、8つ右が終了位置になります。そして、前回の検索範囲が 9個で、今回が 5個なので、差分の 4個を「"6" より小さいもの」とカウントします。ここまで、"6" より大きいものが 7個、小さいものが 4個となっています。

今回は、上から3ビット目が "0" か "1" かを見ます。"6" の上から 3ビット目は "1" なので、次の検索範囲を決めるため、赤線・青線それぞれについて、左にある "1" の数を数えます。すると、9個と 13個なので、次のレベルでの検索位置は、"1" の開始位置である中心線から、それぞれ右に 9 と 13 移動した場所ということになります。

4レベル目は次のようになります。前回の範囲が 5個で、今回の範囲が 4個なので、差分の 1個を「"6" より小さいもの」とカウントします。ここまで、"6" より大きいものが 7個、小さいものが 5個です。

ここが最後のレベルなのですが、下にもう 1つ仮想的なレベルがあると考えて、赤線・青線の位置を考えます。今回、"6" の上から 4ビット目、つまり一番下のビットは "0" なので、赤線・青線それぞれについて、左にある "0" の数を調べます。それぞれ 11・13個なので、図で表すと次の位置になり、その範囲は 2個分です。

今回、キーである "6" の一番下のビットは "0" なので、今の範囲と次の範囲の差分である 2 を「"6" より大きいもの」とカウントします。すると、"6" より大きいものが 9個、小さいものが 5個となります。そして、今回の範囲の広さである 2 は、図で表したように、"6" そのものの数となります。

これで、与えられた範囲の中に、「"6" より小さいもの」・「"6" そのもの」・「"6" より大きいもの」がそれぞれいくつあるかが求められたことになります。