van Emde Boas Trees を実装する - でも今日はSRMあるから

はじめに

Introduction to Algorithms に載ってる、wikipedia:en:Van_Emde_Boas_tree の記事がある、日本語のslideshare Nazoki がある、のでそこそこ知名度がある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ができる。

使い方

コンストラクタにn <= 2^24の値をあげると0~n-1の整数の集合として扱う
初期値は空
sizeやコピーコンストラクタ、デストラクタは無い
next / prev / min / max は値が存在しない場合はINVALID (= 2^32 - 1) を返す
insert / eraseは要素の有無が変更された場合trueを返す
keyはunsignedなのでnext(-1)などやってはならない
clearしたら解放し、もう使うことはできない

int main() {
    VEB veb(100);

    veb.insert(3);
    veb.insert(5);
    veb.insert(8);
    veb.insert(13);

    if (!veb.empty()) puts("not empty");

    if (veb.find(3)) puts("I have 3.");

    if (veb.next(4) != veb.INVALID) printf("next(4) is %u\n", veb.next(4));
    if (veb.next(5) != veb.INVALID) printf("next(5) is %u\n", veb.next(5));

    if (veb.prev(4) != veb.INVALID) printf("prev(4) is %u\n", veb.prev(4));
    if (veb.prev(3) == veb.INVALID) printf("prev(3) is INVALID (%u)\n", veb.prev(3));

    veb.erase(3);
    puts("erase(3)");

    if (veb.min() != veb.INVALID && veb.max() != veb.INVALID)
        printf("min %u, max %u\n\n", veb.min(), veb.max());

    unsigned u = veb.min();
    while (u != veb.INVALID) {
        printf("I have %u\n", u);
        u = veb.next(u);
    }

    veb.clear();

    return 0;
}

出力

not empty
I have 3.
next(4) is 5
next(5) is 8
prev(4) is 3
prev(3) is INVALID (4294967295)
erase(3)
min 5, max 13

I have 5
I have 8
I have 13

実装

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を使用してよいかどうかの考察・覚悟が必要になる。適していない。