Treaps

proof of complexity (let all values be $1\dot{.}.n$): $y$ is an ancestor of $x$ iff $y$ is the lowest among all values in the range $[\min (x,y),\max (x,y)]$. This is with probability $\frac{1}{|y-x+1|}$. Summing this over all $y$ for a fixed $x$ means the expected number of ancestors is just $2\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}\dots \frac{1}{n}\right)$, which is $2\log n+\mathcal{O}(1)$