whoashish's cp notes

Libraries

3 min read

Which code you can rely on already existing, and which you must carry yourself.

The three that matter

LibraryProvidesAvailability
STLcontainers (vector, map, set, priority_queue), algorithms (sort, lower_bound, next_permutation)everywhere
GNU PBDSorder-statistics tree, alternative hash tablesGCC only — Codeforces, AtCoder, most judges
ACL (AtCoder Library)DSU, Fenwick, segment tree, lazy segment tree, max flow, MCMF, SCC, 2-SAT, NTT convolution, modint, string algorithmsAtCoder natively; elsewhere by pasting

Between them these cover almost everything a contest needs. They are complementary rather than overlapping: the STL has no DSU and no segment tree, and ACL has no containers.

What PBDS adds

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  • order_of_key(x) — how many elements are less than
  • find_by_order(k) — the -th smallest

Both . That is a genuinely useful structure the STL simply lacks; see Ordered Set. gp_hash_table is also noticeably faster than unordered_map, though it needs the same custom hash to be safe from anti-hash tests.

oset is a set, not a multiset

Duplicates are silently dropped. The usual workaround is to store pair<value, uniqueIndex> and compare lexicographically.

What ACL adds

DSU, Fenwick, segment tree, lazy segment tree, max flow (Dinic), min-cost flow, SCC, 2-SAT, NTT convolution, modint, and suffix arrays / Z-algorithm. It is well tested and short. On AtCoder it is available with #include <atcoder/all>; elsewhere the source is small enough to paste the one part you need.

It is worth reading even if you never use it — the lazy segment tree and modint in particular are unusually clean designs.

The others

LibraryVerdict
KACTL (KTH)not a compiler library — a curated set of very concise implementations, and the best single thing to read for ICPC preparation
Boostoccasionally useful (multiprecision, graph), rarely available, rarely needed
cp-algorithmsa reference site, not a library; the explanations are the value
Your own templatethe one that actually matters — see Contest Templates

What strong competitors actually use

STL, PBDS occasionally, ACL or their own equivalents, and a personal template of macros and tested implementations. Almost nothing external. The reason is practical: a library you did not write is a library you cannot debug at minute 90 of a contest.

The order to learn them

  1. STL — thoroughly, including the algorithm header
  2. PBDS — the ordered set, in an afternoon
  3. ACL — read the source of the structures you already understand
  4. KACTL — read for the compression tricks, paste sparingly

After that, further progress comes from algorithms and problem-solving, not from more libraries.

See also: STL Containers · Library Snippets · Tools · Ordered Set

Graph View