van Emde Boas tree

#include <cstdio>
#include <ctime>

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int Infinity = 1000000000;

class EmdeBoasTree
{
    private:
        int keySize, min, max;
        EmdeBoasTree **ch, *aux;

    public:
        EmdeBoasTree(int nSize)
        {
            keySize = nSize;
            min = Infinity, max = -Infinity;
            ch = 0;
            if (keySize != 1)
            {
                ch = new EmdeBoasTree* [1 << (keySize >> 1)];
                fill(ch, ch + (1 << (keySize >> 1)), nullptr);
            }
            aux = 0;
        }
        ~EmdeBoasTree()
        {
            delete aux;
            for (size_t i = 0; i < (1 << (keySize >> 1)); i++)
                if (ch[i]) delete ch[i];
            delete ch;
        }

        bool empty()
        {
            return min > max;
        }

        void insert(int x)
        {
            if (empty()) return void(min = max = x);
            if (min == max)
            {
                if (x < min) min = x;
                if (x > max) max = x;
                return;
            }
            if (x < min) swap(x, min);
            if (x > max) swap(x, max);
            int hi = x >> keySize / 2, lo = x - (hi << keySize / 2);
            if (!ch[hi]) ch[hi] = new EmdeBoasTree(keySize / 2);
            ch[hi]->insert(lo);
            if (ch[hi]->min == ch[hi]->max)
            {
                if (!aux) aux = new EmdeBoasTree(keySize / 2);
                aux->insert(hi);
            }
        }

        void erase(int x)
        {
            if (empty()) return;
            if (min == max && min == x)
            {
                min = Infinity, max = -Infinity;
                return;
            }
            if (min == x)
            {
                if (!aux || aux->empty())
                    return void(min = max);
                else
                    x = ch[aux->min]->min, min = x;
            }
            if (max == x)
            {
                if (!aux || aux->empty())
                    return void(max = min);
                else
                    x = ch[aux->max]->max, max = x;
            }
            if (!aux || aux->empty()) return;
            int hi = x >> keySize / 2, lo = x - (hi << keySize / 2);
            if (!ch[hi]) ch[hi] = new EmdeBoasTree(keySize / 2);
            ch[hi]->erase(lo);
            if (ch[hi]->empty()) aux->erase(hi);
        }

        bool contain(int x)
        {
            if (empty()) return false;
            if (x == min || x == max) return true;
            int hi = x >> keySize / 2, lo = x - (hi << keySize / 2);
            if (!ch[hi]) return false;
            return ch[hi]->contain(lo);
        }
};

int main()
{
    freopen("emdeboas.in", "r", stdin);
//     freopen("emdeboas.out", "w", stdout);
    int m = 20000000;
#ifdef EMDE_BOAS
    EmdeBoasTree *t = new EmdeBoasTree(32);
    for (int i = 0; i < m;
    t->insert(i ^ 981838913);
#else
    set<int> s;
    for (int i = 0; i < m; i++)
        s.insert(i ^ 981838913);
#endif
    cout << "Time: " << clock() / 1000 << " ms." << endl;
    return 0;
}