Skip to content

Data Structures

Core

This area is for reusable tools that turn repeated work into fast queries, updates, merges, or ordered-set operations.

The Main Choice In This Area

Most data-structure mistakes come from reaching for something heavier than the invariant actually needs.

  • if the state is just connected components, start with DSU
  • if the state is prefix-style aggregation, start with Fenwick Tree
  • if the state needs general segment decomposition, move to Segment Tree
  • if the real invariant is monotone boundaries or sliding extrema, use Monotonic Stack / Queue
  • if the real state is one ordered set with rank or predecessor logic, move toward PBDS, treap, or splay

Use This Area When

  • recomputing from scratch is clearly too slow
  • the real state is one array, set, component partition, or interval family
  • you need to choose between lighter and heavier query/update tools on purpose

Start With One Route

If your bottleneck is... Open first Then
connectivity and components DSU Fenwick Tree or Segment Tree
range sums and point updates Fenwick Tree Segment Tree, then Lazy Segment Tree
monotone scans and sliding extrema Monotonic Stack / Queue the corresponding ladder and one nearest-boundary anchor
rank, k-th, or ordered-set surgery PBDS / Order Statistics Tree Treap / Implicit Treap, then Splay Tree if needed

Core Progression

  1. Core first
  2. DSU
  3. Fenwick Tree
  4. Segment Tree
  5. Monotonic Stack / Queue

  6. Heaps and Ordered Sets

  7. Then add

  8. Lazy Segment Tree / Sparse Table
  9. PBDS / Order Statistics Tree
  10. Binary Trie / XOR Queries

  11. Offline Tricks / Mo's Algorithm

  12. Deep later

  13. DSU Rollback / DSU On Tree
  14. Treap / Persistent Treap / Persistent Data Structures
  15. Wavelet Tree / Segment Tree Beats / ODT
  16. Interval Trees / Pairing-Leftist Heap / Splay Tree
  17. B-Trees / Skip Lists / X-Fast / Y-Fast Tries as textbook breadth

Good First Repo Anchors

Browse All Subtopics

Go Deeper