Re: An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 3:29 PM, Dmitry Olshansky wrote:

Reminds me of Van Emde Boas layout which is however fractal in nature:
sqrt(N) pieces each having sqrt(N) element are subdivided again into
sqrt(sqrt(N)) pieces and so on.

Not sure if you have seen, but see also cache-oblivious data-structures:
http://erikdemaine.org/papers/BRICS2002/paper.pdf

Thanks, I'll look these up! -- Andrei