はじめに
Introduction to Algorithms に載ってる、wikipedia:en:Van_Emde_Boas_tree の記事がある、日本語のslideshare Nazoki | PPT がある、のでそこそこ知名度があるvan Emde Boas Trees (vEB)。私の中での解釈はbit vectorを平方分割し、next / prevを付けたデータ構造。
| 赤黒木 (std::set) | vEB | bit vector (std::bitset) | |
|---|---|---|---|
| find | O(log n) | O(log log u) | O(1) |
| insert | O(log n) | O(log log u) | O(1) |
| erase | O(log n) | O(log log u) | O(1) |
| next, prev | O(log n), 平均O(1) | O(log log u) | O(u) |
| min, max | O(1) | O(1) | O(u) |
| メモリ | O(n) | O(u) | O(u) |
vEBとbit vectorは非負整数しかkeyにできない。ここでnは要素数。uはkeyの最大値。整数であるのでO(1)でbit演算も配列の参照もできる、すごい。
setのprevはイテレータ操作が必要でO(log n)保証されてないかもしれないけど普通の実装ならそうでしょう。
目的
n個の非負整数a[0] .. a[n-1] (n <= 1e6, 0 <= a[i] <= 1e6) またはそれ以下のサイズについて、集合の操作 find / insert / erase / next / prev / min / max がstd::setより高速なデータ構造。ついでにemptyとclearができる。
実装
wikipediaの資料から辿って読み漁った。
オリジナルのvEBでは葉が2要素のvEBでその上が4, 16, 256, … だと思う。メモリを節約するために葉を64要素のbit vector実装のvEBとし、その上は4096、16777216。1e7を超えた使いやすいサイズに成るのも嬉しい。
vEBはwikipediaではHeapに分類されている通り、部分木のminの値はノードに保存され、それ以外の値は子が保存する。とにかくこの条件だけ満たすようにinsert / erase を実装する。wikipediaの擬似コードを写すとあまり良くないかも。
余分な値を持たせたくなかったので、高さごとにそれぞれclassを定義する。
vEBはkeyを保存する位置がほぼ固定で、回転もなく、実装は赤黒木に比べかなり易しい印象。
コードはココにある VEB.cpp · GitHub
終わりに
vEBを実装した。コンストラクタ以外はstd::setよりは高速。1e7程度の非負整数しか扱えないのでsetの代替にはできないが、ありうる問題設定だと思う。ただし多くの場合はstd::setで十分TLEに間に合うだろうが。
今回の実装は拡張が不可能。mapにすることもbagにすることもできない。
ノードを必要になるまで作らなければU = 2^64のvEBを作ることもできるがn = 1e6ではsetのほうがかなり速い。またメモリ制限のため配列は使えずHashMapを使う必要があり、問題によってHashMapを使用してよいかどうかの考察・覚悟が必要になる。適していない。
