Data Structures -> Treap / Implicit Treap

Randomized split/merge tree family for ordered-set-by-key treaps and mutable-sequence-by-position implicit treaps.

• Topic slug: data-structures/treap-implicit
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 2
• Repo companion pages: 9
• Curated external problems: 4

Microtopics

• random-priorities
• key-order-statistics
• split-merge
• implicit-key
• subtree-size
• sequence-surgery
• ordered-set-vs-sequence
• pair-key-wrapper

Learning Sources

Source	Type
USACO Guide Treaps	Reference
CP-Algorithms Treap	Reference

Practice Sources

Source	Type
CSES Salary Queries	Practice
CSES Cut and Paste	Practice
CSES Substring Reversals	Practice
Library Checker Dynamic Sequence Range Affine Range Sum	Practice

Repo Companion Material

Material	Type
Treap / Implicit Treap hot sheet	quick reference
Key-based Treap starter route	starter route
Implicit Treap family route	family route
Salary Queries note	anchor note
Cut and Paste note	anchor note
Persistent Treap tutorial	compare point
PBDS / Order Statistics Tree tutorial	compare point
Heaps And Ordered Sets tutorial	compare point
Lazy Segment Tree tutorial	compare point

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Salary Queries	CSES	Medium	Key-Based Treap, Order Statistics	Data-Structure-Heavy; Query-Heavy	Split And Merge; Pair Key Wrapper	Range-Count; Pair-Key-Wrapper	A strong first key-based benchmark where duplicate-safe pair keys and rank differences are the whole story.

Practice

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Cut and Paste	CSES	Hard	Implicit Treap, Sequence Surgery	Data-Structure-Heavy; Modeling-Heavy	Split And Merge; Subtree Sizes; Implicit Position	Split-Merge; Sequence-Edits	The cleanest first benchmark where cut/paste by position becomes a short split/merge script.
Substring Reversals	CSES	Hard	Implicit Treap, Sequence Lazy Tags	Data-Structure-Heavy; String-Like	Split And Merge; Lazy Reversal Tag	Reverse; Lazy-Tag	A direct follow-up once split/merge is trusted and one reverse tag becomes the next natural extension.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Sequence Range Affine Range Sum	Library Checker	Very Hard	Implicit Treap, Advanced	Data-Structure-Heavy; Verification	Lazy Propagation; Split And Merge	Affine-Lazy; Range-Sum	The canonical verifier-style stretch once the implicit-treap family is extended with aggregates and lazy tags.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
CUTANDPASTE	Cut and Paste	primary	hard	-	Note	Code
SALARYQUERIES	Salary Queries	primary	medium	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py