Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 63 ยท Contest Toolkit

PBDS and C++ Contest STL Tricks

Use GNU policy-based data structures in contests: ordered set with find_by_order and order_of_key, hash tables with safe hashes, bitset shifts, plus a Python substitute.

Most of this track uses Python, but a large share of contest programmers write C++, and the C++ standard library hides a few features that are worth knowing even if you code in Python: you will meet them in editorials and other people's solutions. This lesson covers the GNU extension policy-based data structures (PBDS), which gives you an order-statistics tree, plus two more tools that show up constantly: hash tables that cannot be hacked, and bitset.

PBDS is a GCC extension, not standard C++. It works on Codeforces, AtCoder and most judges that use GCC, but not on MSVC. The programs below run on this page with GCC 15.

Why an ordered set is not enough

std::set keeps its elements sorted and finds, inserts and erases in O(log n). But it cannot answer two very natural questions quickly:

  • What is the k-th smallest element currently in the set?
  • How many elements are smaller than x?

With std::set the only way is to walk iterators, which is O(n). Those two questions are exactly what you need for "median of a changing set", "count earlier elements larger than me" (inversions), or "delete the k-th person" (Josephus-style problems). A Fenwick tree over compressed values can do it (see Fenwick and Segment Trees), but a PBDS tree does it without any coordinate compression and supports inserts of arbitrary values online.

The ordered set

The header names are long, so everything is wrapped in one alias:

C++
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>,
                         rb_tree_tag, tree_order_statistics_node_update>;

ordered_set<int> behaves like std::set<int> and adds two members:

Member Meaning Cost
find_by_order(k) iterator to the element with 0-based rank k (end iterator if k >= size) O(log n)
order_of_key(x) number of elements strictly less than x O(log n)

Because tree stores unique keys, a multiset is built by storing pairs (value, id) where id is a unique counter or the index. Then the number of copies of v is order_of_key({v, INF}) - order_of_key({v, -INF}).

C++ Ordered set: ranks, multiset and inversions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Read the output against the code. order_of_key(35) is 3 because 10, 20 and 30 are below 35, even though 35 is not in the set. In the inversion count, seen.size() - order_of_key({b[i], INT_MAX}) is the number of earlier elements that are strictly greater than b[i], since every pair (b[i], j) with the same value sorts below (b[i], INT_MAX).

A few cautions:

  • find_by_order returns s.end() when the rank is out of range. Dereferencing it is undefined behavior, so check k < s.size().
  • erase(value) removes by key. To delete one copy from a multiset-by-pairs, erase the pair or the iterator you got from find_by_order.
  • std::lower_bound(s.begin(), s.end(), x) is O(n) on a tree, because the iterators are not random-access. Use the member s.lower_bound(x).
  • The tree is not as fast as a Fenwick tree. For n = 10^6 operations prefer the Fenwick tree when values are known in advance.

Hash tables, and why unordered_map gets hacked

std::unordered_map with the default hash for integers is the identity. On sites with open hacking, someone can submit a test where thousands of keys collide in the same bucket, and your O(1) operations become O(n). The standard remedy is a custom hash with a random salt that is fixed when the program starts. A good mixer is the splitmix64 function.

PBDS offers gp_hash_table, which is often two to three times faster than unordered_map. It takes the hash as a third template argument. Below it is used with a salted splitmix hash, together with bitset.

bitset: 64 booleans per machine word

bitset<N> stores N bits in about N / 64 words. Bulk operations (|, &, ^, shifts, count()) process 64 bits per instruction, so a loop that would cost N steps costs N / 64. The two classic uses are subset-sum reachability and set intersections:

C++
reach |= reach << w;   // every reachable sum s becomes reachable at s + w too

_Find_first() and _Find_next(i) are GCC extensions that walk the set bits quickly.

C++ gp_hash_table with a safe hash, and bitset knapsack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The subset-sum line runs in n * (N / 64) time. With N = 10^5 and n = 1000 items that is about 1.5 million word operations, a small fraction of what the plain DP would need.

The same idea in Python

Python has no PBDS, but you can get the two order-statistics operations with a Fenwick tree over compressed values. You need all the values in advance (or you work offline). order_of_key(x) counts the elements below x, and find_by_order(k) walks down the tree using the powers of two, which is the standard "Fenwick descent".

Python Order statistics in Python with a Fenwick tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For an online problem where the values are not known in advance, Python programmers use a SortedList from a library (not available on most judges) or a sqrt-decomposed list. That is one reason many of these problems are easier in C++.

When to reach for each tool

  • Need k-th or rank on a changing set with arbitrary values: PBDS ordered_set (C++), or a Fenwick tree when you can compress offline.
  • Need to count or look up many integer keys: gp_hash_table or unordered_map with a salted hash.
  • Need a large boolean DP or set intersections: bitset.
  • Everything else: plain std::set, std::map and std::vector are simpler and often just as fast.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does order_of_key(x) return for an ordered_set?

    order_of_key counts strictly smaller elements and works for any x, even one that is not stored.
  2. 2. How do you store duplicates in a PBDS tree?

    The tree holds unique keys. Pairing the value with a unique id makes every key distinct and lets you count copies by rank differences.
  3. 3. Why use a salted custom hash with unordered_map or gp_hash_table on Codeforces?

    The default integer hash is predictable, so a hacker can craft keys that land in one bucket and push the running time to O(n) per operation.
  4. 4. What does reach |= reach << w do in a bitset subset-sum?

    Shifting by w moves each reachable sum s to s + w, and OR keeps the old sums, so the item may be used or skipped.

Summary

  • PBDS tree with tree_order_statistics_node_update adds find_by_order(k) and order_of_key(x) to a set, each in O(log n).
  • A multiset is a set of (value, id) pairs; use the member lower_bound, never std::lower_bound, on a tree.
  • Protect hash tables from anti-hash tests with a salted splitmix hash; gp_hash_table is a fast drop-in.
  • bitset does 64 boolean operations at once: subset sums become reach |= reach << w.
  • In Python, a Fenwick tree over compressed values gives the same rank and k-th operations offline.

Next: Implementation Problems