05 — Template Library¶
In a 2-hour contest, you cannot afford to debug your Union-Find implementation from scratch. You also can’t afford to second-guess your binary search boundaries or your Dijkstra priority queue comparator. The purpose of a template library is to eliminate implementation uncertainty from the contest environment — every template in your library is a piece of code you’ve already verified on real problems, with known behavior, that you can drop in without thinking. This file gives you language-agnostic specifications and tested C++ implementations for the core templates.
Why Templates (And Why They Can Go Wrong)¶
Templates are tools, not crutches. The risk is this: you template something, paste it in, and trust it without understanding it. Then it fails on a problem with slightly different requirements and you have no idea why. Template hygiene prevents this.
The three rules of template hygiene:
Comment every template explaining what it does, its invariants, and its complexity.
Test every template on at least one known problem before using it in a rated contest.
Add a template to your library only after you’ve used the underlying logic in 3+ problems. Before that, you’re still in learning mode — write it from scratch.
The third rule is the one that matters. A template you copied from the internet and never used is a liability. A template you built from your own problems, that you’ve debugged, that you understand edge-to-edge — that’s an asset.
Template 1: Disjoint Set Union (DSU / Union-Find)¶
What it does: Maintains a partition of n elements into disjoint sets. Supports union (merge two sets) and find (which set does this element belong to?) in near-O(1) amortized time with path compression + union by rank.
Invariants: parent[x] = x iff x is root. rank[x] is an upper bound on tree height.
Complexity: O(α(n)) per operation (inverse Ackermann — effectively O(1)).
struct DSU {
vector<int> parent, rank_;
int components;
DSU(int n) : parent(n), rank_(n, 0), components(n) {
iota(parent.begin(), parent.end(), 0); // parent[i] = i
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false; // already same component
if (rank_[x] < rank_[y]) swap(x, y);
parent[y] = x;
if (rank_[x] == rank_[y]) rank_[x]++;
components--;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
};
// Usage:
// DSU dsu(n);
// dsu.unite(u, v);
// if (dsu.connected(a, b)) { ... }
// dsu.components // number of connected components
Verify on: LC 684 (Redundant Connection), LC 547 (Number of Provinces), CF 1033C.
Template 2: Segment Tree (Point Update, Range Query)¶
What it does: Supports point updates and range aggregate queries (sum, min, max) in O(log n).
Invariants: tree[1] is the root covering [0, n-1]. tree[i]’s children are tree[2i] and tree[2i+1].
Complexity: O(n) build, O(log n) update and query.
struct SegTree {
int n;
vector<long long> tree;
SegTree(int n) : n(n), tree(4 * n, 0) {}
void update(int node, int lo, int hi, int pos, long long val) {
if (lo == hi) { tree[node] = val; return; }
int mid = (lo + hi) / 2;
if (pos <= mid) update(2*node, lo, mid, pos, val);
else update(2*node+1, mid+1, hi, pos, val);
tree[node] = tree[2*node] + tree[2*node+1]; // change for min/max
}
long long query(int node, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0; // identity for sum; INT_MAX for min
if (l <= lo && hi <= r) return tree[node];
int mid = (lo + hi) / 2;
return query(2*node, lo, mid, l, r) + query(2*node+1, mid+1, hi, l, r);
}
// Convenience wrappers
void update(int pos, long long val) { update(1, 0, n-1, pos, val); }
long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};
// Usage:
// SegTree st(n);
// st.update(i, val);
// long long ans = st.query(l, r);
Verify on: LC 307 (Range Sum Query Mutable), LC 315 (Count of Smaller Numbers After Self).
Template 3: Fenwick Tree / BIT (Point Update, Prefix Sum Query)¶
What it does: Simpler than segment tree. Supports point updates and prefix sum queries in O(log n). Use this when you only need prefix sums — it’s ~3x faster and 5x less code.
struct BIT {
int n;
vector<long long> tree;
BIT(int n) : n(n), tree(n + 1, 0) {}
void update(int i, long long delta) { // 1-indexed
for (++i; i <= n; i += i & -i)
tree[i] += delta;
}
long long query(int i) { // prefix sum [0, i], 0-indexed
long long sum = 0;
for (++i; i > 0; i -= i & -i)
sum += tree[i];
return sum;
}
long long query(int l, int r) { // range sum [l, r], 0-indexed
return query(r) - (l > 0 ? query(l - 1) : 0);
}
};
Verify on: LC 307, LC 493 (Reverse Pairs), LC 1649 (Create Sorted Array Through Instructions).
Template 4: Dijkstra (Shortest Path, Non-Negative Weights)¶
What it does: Finds single-source shortest paths in a weighted graph with non-negative edge weights. O((V + E) log V).
const long long INF = 1e18;
vector<long long> dijkstra(int src, int n, vector<vector<pair<int,int>>>& adj) {
// adj[u] = {(v, w)} meaning edge u -> v with weight w
vector<long long> dist(n, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry — skip
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist; // dist[i] = shortest distance from src to i; INF if unreachable
}
// Usage:
// int n = number_of_nodes;
// vector<vector<pair<int,int>>> adj(n);
// adj[u].push_back({v, w});
// auto dist = dijkstra(source, n, adj);
Verify on: LC 743 (Network Delay Time), LC 1514 (Path with Maximum Probability), CF 20C.
Template 5: KMP String Matching¶
What it does: Finds all occurrences of pattern P in text T in O(|T| + |P|). Failure function encodes the longest proper prefix-suffix at each position.
vector<int> kmp_failure(const string& p) {
int m = p.size();
vector<int> fail(m, 0);
for (int i = 1; i < m; i++) {
int j = fail[i - 1];
while (j > 0 && p[i] != p[j]) j = fail[j - 1];
if (p[i] == p[j]) j++;
fail[i] = j;
}
return fail;
}
vector<int> kmp_search(const string& text, const string& pattern) {
// Returns all starting indices (0-indexed) of pattern in text
string combined = pattern + "#" + text;
vector<int> fail = kmp_failure(combined);
int m = pattern.size();
vector<int> matches;
for (int i = m + 1; i < (int)combined.size(); i++) {
if (fail[i] == m)
matches.push_back(i - 2 * m); // starting index in text
}
return matches;
}
Verify on: LC 28 (Find the Index of the First Occurrence), LC 214 (Shortest Palindrome), LC 459 (Repeated Substring Pattern).
Template 6: Binary Search (Generic)¶
What it does: Finds the first index where a condition becomes true over a monotone boolean predicate. The single most reusable template — works for search on arrays, search on answer space, and more.
// Returns the smallest index in [lo, hi] where condition(mid) is true.
// Precondition: condition is monotone (false...false...true...true).
// If no such index exists, returns hi + 1.
template<typename F>
int binary_search_first_true(int lo, int hi, F condition) {
int result = hi + 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow
if (condition(mid)) {
result = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return result;
}
// Example: find first index where arr[i] >= target
// int idx = binary_search_first_true(0, n-1, [&](int m){ return arr[m] >= target; });
// Example: binary search on answer — minimum k such that feasible(k) is true
// int k = binary_search_first_true(0, MAX_VAL, [&](int m){ return feasible(m); });
Verify on: LC 35 (Search Insert Position), LC 875 (Koko Eating Bananas), LC 1011 (Capacity to Ship Packages).
Template 7: Modular Arithmetic Helpers¶
What it does: Modular exponentiation and modular inverse (used whenever the problem says “answer modulo 10⁹+7”).
const long long MOD = 1e9 + 7;
long long mod_pow(long long base, long long exp, long long mod = MOD) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
// Modular inverse using Fermat's little theorem (mod must be prime)
long long mod_inv(long long a, long long mod = MOD) {
return mod_pow(a, mod - 2, mod);
}
// Safe modular addition (avoids intermediate overflow)
long long mod_add(long long a, long long b, long long mod = MOD) {
return (a % mod + b % mod) % mod;
}
// Safe modular multiplication
long long mod_mul(long long a, long long b, long long mod = MOD) {
return (a % mod) * (b % mod) % mod;
}
// Safe subtraction (avoids negative result)
long long mod_sub(long long a, long long b, long long mod = MOD) {
return ((a - b) % mod + mod) % mod;
}
Verify on: LC 50 (Pow(x, n)), LC 1916 (Count Ways to Build Rooms in an Ant Colony), any combinatorics problem with modular inverse.
Building Your Library Incrementally¶
Don’t copy all of these into a file right now and call it done. That’s not a template library — that’s a buffer you won’t trust or remember.
The correct process:
Solve a problem that requires Union-Find. Implement it from scratch. Get it working.
Solve two more Union-Find problems. Same implementation, refined.
On the fourth problem, extract your implementation into
templates/dsu.cpp. Comment it. Note which 3 problems verified it.Now it’s a template you trust.
Repeat for each structure. By the end of Phase 6, you should have 5-8 trusted templates. That’s the right number — more than 10 and you’ve templated things you don’t actually understand yet.
What Most People Get Wrong¶
Most people template too early and too broadly. They download a 500-line competitive programming template from GitHub, paste it at the top of every solution, and develop false confidence that they have all the tools. They don’t — they have code they don’t understand.
The second mistake is never writing templates at all, insisting on writing from scratch every time as a “purity” principle. This is noble until minute 90 of a 120-minute contest when you’re debugging your Union-Find rank comparison for the fourth time this month.
The sweet spot is templates you built yourself, from problems you solved, that you can read and explain in under 30 seconds. Own the code. Don’t rent it.