Skip to content

PBDS / Order Statistics Tree Ladder

This lane is for the first time one dynamic ordered set needs rank or k-th queries online, not just predecessor or successor.

Who This Is For

Use this lane if:

  • Heaps And Ordered Sets already feels comfortable
  • you can explain why set and multiset keep one global order
  • you now need how many are smaller than x? or what is the k-th alive value?

This lane is intentionally narrow:

  • one exact starter
  • one flagship note that is pure order-statistics
  • one duplicate-safe compare route
  • one find_by_order elimination compare route

Warm-Up

  • explain why predecessor is not the same as rank
  • explain why k-th smallest cannot be retrieved efficiently from plain std::set
  • hand-simulate order_of_key(8) and find_by_order(1) on {2, 7, 10}

Target skill:

  • recognize when the missing operation is subtree-size-aware order statistics, not general ordered-set syntax

Warm-up compare points:

Core

Target skill:

  • use order_of_key and find_by_order without mixing up one-based and zero-based indexing

Stretch

Target skill:

  • distinguish unique-key PBDS, duplicate-safe pair wrappers, and compressed-frequency alternatives

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. reopen Heaps And Ordered Sets just enough to trust that predecessor is not enough
  2. learn the exact rank / k-th route in PBDS / Order Statistics Tree
  3. solve ORDERSET - Order Statistic Set
  4. compare the pure set route against duplicates in Salary Queries and against find_by_order elimination in Josephus Problem II

Exit Criteria

You are ready to move on when:

  • you can state the difference between order_of_key(x) and predecessor queries
  • you remember that find_by_order is zero-based
  • you know why duplicates need a pair-key wrapper
  • you can tell when PBDS is overkill because Fenwick or multiset already closes the task

External Practice