Implicit Treaps

Implicit treaps don't store explicit keys. Instead, the "key" is the position in the in-order traversal, computed on the fly from subtree sizes.

Each node stores $size$ = number of nodes in its subtree. The position of a node is the count of nodes before it in in-order.

This approach enables array-like operations:

• Insert at position $i$
• Delete at position $i$
• Reverse a range $[l, r]$
• Cyclic shift

All in $O(\log n)$ expected time. Implicit treaps are like super-powered dynamic arrays.