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

[Timon Gehr via Digitalmars-d]

On 12/02/2015 12:26 PM, Timon Gehr wrote:
> ...
> ∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
> =
> ∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
>

It should actually be (⌊i/2⌋-1)² here, but this does not change the 
asymptotics.