Skip to content

Data Structures Cheatsheet

Use this page when you know the operations but have not yet picked the lightest structure.

Do Not Use When

  • the main difficulty is graph or DP modeling rather than operations
  • one static formula or prefix array already solves the whole problem
  • you still cannot list the required operations cleanly

Choose By Operations

First Questions

  • static or dynamic?
  • prefix-only or arbitrary range?
  • online or offline?
  • duplicates matter?
  • do you need order, rank, or only the current best element?

Core Invariants

  • Fenwick / prefix structures: one stable prefix meaning
  • segment tree: every node represents one mergeable segment summary
  • persistent segment tree: every version is one root and untouched subtrees are shared
  • DSU: every element belongs to one representative-led component
  • rollback DSU: the current component forest must be exactly restorable from snapshots
  • ordered-set logic: duplicates and erase policy must be explicit

Retrieval Cues

Quick Anchors In This Repo

Common Mistakes

  • using a segment tree when the query is static
  • mutating a shared node and corrupting an old version
  • forgetting that set drops duplicates
  • trying to erase arbitrary heap items without a lazy-delete plan
  • missing the original-order bookkeeping in offline processing

Do Not Overbuild

Under contest pressure, the usual failure is not “too simple.” It is “picked a heavier structure than the operations justify.”

Ask:

  • would prefix sums already work?
  • would sorting + two pointers already work?
  • are all queries known first, so offline processing is enough?

Next Stops