van Emde Boas Tree

個人的メモ

y fast trie と比べて実装が楽かつ最悪計算量を保証している点が優れている. おそらく実測もこちらのほうが速いが, 空間計算量が要素数ではなく, 値域分だけ必要である点が劣っている.
実装は再帰的に書けるので比較的容易だが, 愚直に実装すると時間的にもメモリ的にも効率が悪くなってしまう.
2 つ目の実装については $1$ 層目は $2^{24}$ 個のブロックに分割し, 各ブロックは uint64_t で管理して長さ $2^{24}$ の summary を次の層でまたブロック分割する. メモリ削減のため $1$ 層目の各ブロックは $\max, \min$ の変数を持たないようにしている.
$2$ 層目は $2^{12}$ 個のブロックに分割し, 各ブロック, summary ともに長さ $2^{12}$ となりそれをまた次の層でブロック分割する.
$3$ 層目は $2^6$ 個のブロックに分割し, 各ブロック, summary ともに長さ $2^6$ となりこれらを uint64_t で管理している. こちらも uint64_t で表されるデータブロックについてはメモリを削減するために $\max, \min$ は保持していない.
$2$ べきにすることで各層で除算, 乗算を行わずにビット演算で済ませることができ, またある程度要素が増えてくるとクエリの処理が $1$ 層目で終了することも多くなり, そういった場合はとても高速に動作する.