Skip to content

Treap / Implicit Treap Hot Sheet

Use this page when one mutable sequence needs split / merge by position or one ordered set needs split / merge by key.

Do Not Use When

  • std::set / multiset already solves the task with predecessor / successor / erase-one
  • GNU PBDS already solves online rank / k-th more simply -> Order Statistics Tree hot sheet
  • the sequence length is fixed and the real task is interval aggregate/update -> Lazy Segment Tree hot sheet
  • the array is static
  • you still think the node's position should be stored explicitly in an implicit treap

Choose By Signal

  • ordered keys, but split/merge by key is the whole trick -> key-based treap
  • one ordered set needs online rank / k-th, but you want a self-hosted route instead of GNU PBDS -> key-based treap
  • insert / erase / cut / paste by position in a mutable sequence -> implicit treap
  • old list versions stay alive and new edits are still split/merge sequence surgery -> Persistent Treap hot sheet
  • fixed-length array with range aggregate/update -> Segment Tree hot sheet or Lazy Segment Tree hot sheet
  • simple predecessor / successor / erase-one -> Heaps and ordered sets topic

Core Invariants

  • ordinary treap keeps BST order on keys and heap order on random priorities
  • implicit treap replaces explicit key comparisons with subtree-size counting
  • split(root, x) in the key-based route means keys < x vs >= x
  • split(root, k) in the implicit route means first k elements vs the rest
  • every child rewrite must repair subtree size with pull

Main Traps

  • storing explicit indices in an implicit treap
  • forgetting whether your split convention is < x vs >= x, or first k vs rest
  • treating the starter as if it already had range-sum / reverse / lazy-tag support
  • using treap when PBDS, ordered set, or segment tree is simpler

Exact Starter Routes

Reopen Paths