Treap Without A Key

A skip list keyed by value: search by key rather than by rank, so a node's position follows from its key. All four are $O(\log n)$ expected, with reversal as a lazy flag.

An implicit treap: split by subtree size rather than by value, so a node's position is its in-order rank. All four are $O(\log n)$ expected, with reversal as a lazy flag.

A Fenwick tree over positions: index by prefix count rather than by value, so a node's position is a prefix sum. All four are $O(\log n)$ worst case, with reversal handled by a second Fenwick.

A lazy segment tree over positions: address by leaf slot rather than by value, so a node's position is its leaf index. All four are $O(\log n)$ worst case, with insertion into the next free leaf.