Van Emde Boas Trees

Our universe is full of natural numbers.

U={0,1,2,・・・U-1}

There are O(1) machine words in U.

S is the element of U.

・insert(x) is adding x to S.
・empty() is S=φ.
・lookup(x) is x∊S.
・delete(x) is removing x from S.
・max() and min() are the maximum or minimum element of S.

A bitvector is an array of bits of length U.

・insert(x) is setting the bit for x to 1.
・delete(x) is setting the bit for x to 0.
・lookup(x) is checking whether the bit for x is 1.

Space usage is Θ (U).
110011000111111000

This is quite slow. O(1) is faster than O(logU).

000010000 This is O(1) which is easy to find.

Break the universe (U) into Θ( U / B) blocks of size B. It is Tiered Bitvectors.

Data structure that supports each of the following operations in O(log log U) time, where all keys belong to the range {0, 1, ..., U-1}.
U=2^m (m is natural numbers)

There are O(log2 16)=4 operations, and min and max are √4=log2 4.

Internal nodes can be seen as an an array summary[0 .. √U–1］.

T(m)=T(m/2)+O(1)

You see hash tables O(n), (0,1,2,3,4・・・・). O(1) is fast to reach your purpose.