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

[Andrei Alexandrescu via Digitalmars-d]

On 12/01/2015 04:50 AM, Emil Kirschner wrote:
> On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
>> Okasaki's book is a continued inspiration of data structures and
>> algorithms.
>> Start with a simple array of data. Then mentally decompose that array
>> into a concatenation of smaller arrays: first has size 1, second has
>> size 4, third has size 9, then 16, 25, 36, ... Generally the size of
>> these imaginary subarrays grows quadratically. And they're adjacent to
>> each other. The last array may be incomplete.
>> ........
>> Please share any thoughts!
>>
>>
>> Andrei
>
> Interesting, but isn't that basically a skip list with uneven sub-lists?
> insert could be quite complex unless the entire data structure is backed
> by a continuous or a continuous linked list.

Doesn't look like a skip list to me. -- Andrei