64分木で集合の最小値を高速でみつける

あるときABC218GのFastestをみたらtatyamさんが取っていました。中身を見たらよくわからないデータ構造を使っていて、どうやらnoshi91さんのものであるようでした。
Submission #25860371 - AtCoder Beginner Contest 218

コードを見たり検索したりして、どうやら「64分木」なるデータ構造のようだとわかりました。
雰囲気は理解した気になったので、集合の最小値を高速でみつける64分木らしきクラスを書き、無理やりABC218GのFastestを取りました。
Submission #27488760 - AtCoder Beginner Contest 218

tatyamさんの提出を見ると、64分木では本来は「指定範囲内での最小値」とかも読めるようで、64分木の部分はtatyamさんのほうがエレガントで高速のように思えます。(私の入力とソートが高速で結果的にFastestが取れている)
とりあえず今回は、集合全体の最小値を高速でみつけるだけのクラスを書いたので、メモとして残します。

以下が私が書いたクラスです。

typedef long long ll;
class hoge {
public:
	ll A0, A1[1 << 6], A2[1 << 12];
	hoge() : A0(), A1(), A2() { }
	void push(int a) {
		A2[a >> 6] |= 1ll << (a & 63);
		A1[a >> 12] |= 1ll << (a >> 6 & 63);
		A0 |= 1ll << (a >> 12);
	}
	void erase(int a) {
		A2[a >> 6] ^= 1ll << (a & 63);
		A1[a >> 12] ^= (ll)!A2[a >> 6] << (a >> 6 & 63);
		A0 ^= (ll)!A1[a >> 12] << (a >> 12);
	}
	int top() {
		int ret = __builtin_ctzll(A0);
		ret = ret << 6 | __builtin_ctzll(A1[ret]);
		ret = ret << 6 | __builtin_ctzll(A2[ret]);
		return ret;
	}
}

ほぼ全てがbit演算子という頭が悪いクラスで、if文すら存在しないのでかなり高速だと思われます。
関数は、push(int)とerase(int)とtop()があります。
push(int)では0から262143(2^18-1)までの整数を入力し、集合に加えます。
erase(int)では整数を集合から取り除きます。erase(int)は集合に存在しない数を指定すると壊れます。チェックする機能は持たせていません。
top()では集合にある一番小さい整数を出力します。集合に何もない場合何が返ってくるかわかりません。

入力する整数の大きさに制限がありますが、priority_queueのように使うことができて高速です。しかも任意の要素が削除できるのでその点だけはpriority_queueよりも高性能です。メモリも4000個ちょいのlong longなので省メモリです。もしsortに自信がある方なら、座圧してこのクラスを使ったほうが高速になる可能性を秘めていると思います。

記事はここまでで良いように思うのですが、64分木について少し追記します。
2分木は親が2個の子を持つ木ですが、64分木は64個の子を持つ木です。64を選んだのは例によってlong longが64ビット整数だからで、ビット演算を用いれば立っているビットのうち一番左のビットは何ビット目？といったことが高速にわかります。
よって、部分木に1つでも整数がpushされているとき対応するビットが立つようにしておけば、根からたどって高速で最小値をみつけられます。
深さが1増えると64倍になるので、3回辿るだけで200,000以上の整数まで対応できるのが強いです。