Lessons from Cut and Paste

Important lessons:

$1.$ Implicit treaps turn array index into a computed property from subtree sizes

$2.$ Any sequence rearrangement you can do with split and merge in $O(\log n)$

$3.$ Lazy propagation works with treaps too (for range updates, reversals)

$4.$ Random priorities give expected $O(\log n)$ height without complex balancing

Treaps are the go-to structure for dynamic sequences. Simpler than splay trees, more flexible than segment trees.