Persistent Treap Hot Sheet

Use this sheet when the statement keeps many list or sequence versions alive and the real edits are still split / merge sequence surgery.

Do Not Use When

• the structure is a fixed array and the exact route is path-copying over one segment tree -> Persistent Data Structures hot sheet
• only one current sequence matters -> Treap / Implicit Treap hot sheet
• the real task is an ordered set with no historical versions
• a queue/stack-specific persistent trick is simpler than full split/merge treap

Choose By Signal

• "merge two old lists into a new list" -> persistent treap
• "split one old list into two new lists" -> persistent treap
• "copy array k, then change one position" -> Persistent Data Structures hot sheet
• "cut/paste by position, but only one current sequence exists" -> Treap / Implicit Treap hot sheet

Core Invariants

• one version is one immutable treap root
• implicit positions still come from subtree sizes
• merge and split_prefix clone only the touched recursion path
• untouched subtrees are shared safely between versions
• subtree sum means the sum of exactly that version's represented sequence

Main Traps

• mutating a shared node during split/merge
• forgetting this first route is sequence/list persistence, not fixed-array persistence
• assuming the starter already supports lazy reversal, affine tags, or key-based maps
• mixing "first k elements" semantics with key-based split semantics

Exact Starter Route

• exact starter -> persistent-treap-list-sum.cpp
• flagship in-lane rep -> Persistent List
• compare points -> Persistent Data Structures hot sheet, Treap / Implicit Treap hot sheet

Reopen Paths

• full lesson -> Persistent Treap
• fixed-array persistence -> Persistent Data Structures
• one-current-version split/merge -> Treap / Implicit Treap