Appendix D: Contest-Ready Algorithm Templates

🏆 Quick Reference: These templates are battle-tested, copy-paste ready, and designed to work correctly in competitive programming. Each is annotated with complexity and typical use cases.

Before diving into the templates, use this decision tree to choose the right algorithm based on N:

D.1 DSU / Union-Find

Use when: Dynamic connectivity, Kruskal's MST, cycle detection, grouping elements.

Complexity: O(α(N)) ≈ O(1) per operation.

// =============================================================
// DSU (Disjoint Set Union) with Path Compression + Union by Rank
// =============================================================
struct DSU {
    vector<int> parent, rank_;
    int components;  // number of connected components

    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

    // Find with path compression
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    // Union by rank — returns true if actually merged (different components)
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;  // already connected
        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); }
};

// Example usage:
int main() {
    int n = 5;
    DSU dsu(n);
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    cout << dsu.connected(0, 1) << "\n";  // 1 (true)
    cout << dsu.connected(0, 2) << "\n";  // 0 (false)
    cout << dsu.components << "\n";       // 3
    return 0;
}

D.2 Segment Tree (Point Update, Range Sum)

Use when: Range sum/min/max queries with point updates.

Complexity: O(N) build, O(log N) per query/update.

// =============================================================
// Segment Tree — Point Update, Range Sum Query
// =============================================================
struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(int n) : n(n), tree(4 * n, 0) {}

    void build(vector<long long>& arr, int node, int start, int end) {
        if (start == end) { tree[node] = arr[start]; return; }
        int mid = (start + end) / 2;
        build(arr, 2*node, start, mid);
        build(arr, 2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    void build(vector<long long>& arr) { build(arr, 1, 0, n-1); }

    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) { tree[node] = val; return; }
        int mid = (start + end) / 2;
        if (idx <= mid) update(2*node, start, mid, idx, val);
        else update(2*node+1, mid+1, end, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    // Update arr[idx] = val
    void update(int idx, long long val) { update(1, 0, n-1, idx, val); }

    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;  // identity for sum
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2*node, start, mid, l, r)
             + query(2*node+1, mid+1, end, l, r);
    }
    // Query sum of arr[l..r]
    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};

// Example usage:
int main() {
    vector<long long> arr = {1, 3, 5, 7, 9, 11};
    SegTree st(arr.size());
    st.build(arr);
    cout << st.query(2, 4) << "\n";   // 5+7+9 = 21
    st.update(2, 10);                 // arr[2] = 10
    cout << st.query(2, 4) << "\n";   // 10+7+9 = 26
    return 0;
}

D.3 BFS Template

Use when: Shortest path in unweighted graph/grid, level-order traversal, multi-source distances.

Complexity: O(V + E).

// =============================================================
// BFS — Shortest Path in Unweighted Graph
// =============================================================
#include <bits/stdc++.h>
using namespace std;

// Returns dist[] where dist[v] = shortest distance from src to v
// dist[v] = -1 if unreachable
vector<int> bfs(int src, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// Grid BFS (4-directional)
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

int gridBFS(vector<string>& grid, int sr, int sc, int er, int ec) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return dist[er][ec];  // -1 if unreachable
}

D.4 DFS Template

Use when: Connected components, cycle detection, topological sort, flood fill.

Complexity: O(V + E).

// =============================================================
// DFS — Iterative and Recursive Templates
// =============================================================

vector<vector<int>> adj;
vector<int> color;  // 0=white, 1=gray (in stack), 2=black (done)

// Recursive DFS with cycle detection (directed graph)
bool hasCycle = false;
void dfs(int u) {
    color[u] = 1;  // mark as "in progress"
    for (int v : adj[u]) {
        if (color[v] == 0) dfs(v);
        else if (color[v] == 1) hasCycle = true;  // back edge → cycle!
    }
    color[u] = 2;  // mark as "done"
}

// Topological sort using DFS post-order
vector<int> topoOrder;
void dfsToposort(int u) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 0) dfsToposort(v);
    }
    color[u] = 2;
    topoOrder.push_back(u);  // add to order AFTER processing all children
}
// Reverse topoOrder for correct topological sequence

// Iterative DFS (avoids stack overflow for large graphs)
void dfsIterative(int src, int n) {
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // Process u here
        for (int v : adj[u]) {
            if (!visited[v]) st.push(v);
        }
    }
}

D.5 Dijkstra's Algorithm

Use when: Shortest path in weighted graph with non-negative edge weights.

Complexity: O((V + E) log V).

// =============================================================
// Dijkstra's Shortest Path — O((V+E) log V)
// =============================================================
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, int> pli;  // {distance, node}
const long long INF = 1e18;

vector<long long> dijkstra(int src, int n,
                            vector<vector<pair<int,int>>>& adj) {
    // adj[u] = { {v, weight}, ... }
    vector<long long> dist(n, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;  // min-heap

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > dist[u]) continue;  // ← KEY LINE: skip outdated entries

        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[v] = shortest distance src → v, INF if unreachable
}

// Example usage:
int main() {
    int n = 5;
    vector<vector<pair<int,int>>> adj(n);
    // Add edge u-v with weight w (undirected):
    auto addEdge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    addEdge(0, 1, 4);
    addEdge(0, 2, 1);
    addEdge(2, 1, 2);
    addEdge(1, 3, 1);
    addEdge(2, 3, 5);

    auto dist = dijkstra(0, n, adj);
    cout << dist[3] << "\n";  // 4 (path: 0→2→1→3 with cost 1+2+1=4)
    return 0;
}

D.6 Binary Search Templates

Use when: Searching in sorted arrays, or "binary search on answer" (parametric search).

Complexity: O(log N) per search, O(f(N) × log V) for binary search on answer.

// =============================================================
// Binary Search Templates
// =============================================================

// 1. Find exact value (returns index or -1)
int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 2. First index where arr[i] >= target (lower_bound)
int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // arr.size() if all elements < target
}

// 3. First index where arr[i] > target (upper_bound)
int upperBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 4. Binary search on answer — find maximum X where check(X) is true
// Template: adapt lo, hi, and check() for your problem
long long bsOnAnswer(long long lo, long long hi,
                     function<bool(long long)> check) {
    long long answer = lo - 1;  // sentinel: no valid answer
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            answer = mid;
            lo = mid + 1;  // try to do better
        } else {
            hi = mid - 1;
        }
    }
    return answer;
}

// STL wrappers (prefer these in practice):
// lower_bound(v.begin(), v.end(), x) → iterator to first element >= x
// upper_bound(v.begin(), v.end(), x) → iterator to first element >  x
// binary_search(v.begin(), v.end(), x) → bool, whether x exists

lower_bound / upper_bound cheat sheet:

D.7 Modular Arithmetic Template

Use when: Large numbers, combinatorics, DP with large values.

Complexity: O(1) per operation, O(log exp) for modpow.

// =============================================================
// Modular Arithmetic Template
// =============================================================
const long long MOD = 1e9 + 7;  // or 998244353 for NTT-friendly

long long mod(long long x) { return ((x % MOD) + MOD) % MOD; }
long long add(long long a, long long b) { return (a + b) % MOD; }
long long sub(long long a, long long b) { return mod(a - b); }
long long mul(long long a, long long b) { return a % MOD * (b % MOD) % MOD; }

// Fast power: base^exp mod MOD — O(log exp)
long long power(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;  // if last bit is 1
        base = base * base % mod;                    // square the base
        exp >>= 1;                                   // shift right
    }
    return result;
}

// Modular inverse (base^(MOD-2) mod MOD, only when MOD is prime)
long long inv(long long x) { return power(x, MOD - 2); }

// Modular division
long long divide(long long a, long long b) { return mul(a, inv(b)); }

// Precompute factorials for combinations
const int MAXN = 200005;
long long fact[MAXN], inv_fact[MAXN];

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = inv(fact[MAXN-1]);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

// C(n, k) = n choose k mod MOD
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

D.8 Fast Power (Binary Exponentiation)

Use when: Computing a^b for large b (standalone or modular).

Complexity: O(log b).

// =============================================================
// Binary Exponentiation — a^b in O(log b)
// =============================================================

// Integer power (no mod) — careful of overflow for large a,b
long long fastPow(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) result *= a;  // if current bit is 1
        a *= a;                   // square a
        b >>= 1;                  // next bit
    }
    return result;
}

// Modular power — a^b mod m
long long modPow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

// Matrix exponentiation — M^b for matrix M (for Fibonacci in O(log N) etc.)
typedef vector<vector<long long>> Matrix;
// Note: uses MOD from D.7 (const long long MOD = 1e9 + 7)

Matrix multiply(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (A[i][k])
                for (int j = 0; j < n; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix matPow(Matrix M, long long b) {
    int n = M.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;  // identity matrix
    while (b > 0) {
        if (b & 1) result = multiply(result, M);
        M = multiply(M, M);
        b >>= 1;
    }
    return result;
}

// Example: Fibonacci(N) in O(log N) using matrix exponentiation
// [F(n+1)]   [1 1]^n   [F(1)]
// [F(n)  ] = [1 0]   * [F(0)]
long long fibonacci(long long n) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix result = matPow(M, n - 1);
    return result[0][0];  // F(n)
}

D.9 Other Useful Templates

Prefix Sum (1D and 2D)

// 1D Prefix Sum
vector<long long> prefSum(n + 1, 0);
for (int i = 1; i <= n; i++) prefSum[i] = prefSum[i-1] + arr[i];
// Query sum of arr[l..r] (1-indexed): prefSum[r] - prefSum[l-1]

// 2D Prefix Sum
long long psum[N+1][M+1] = {};
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++)
        psum[i][j] = grid[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];
// Query sum of rectangle [r1,c1]..[r2,c2]:
// psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]

Competitive Programming Header

// Standard competitive programming template
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your solution here
    return 0;
}

Quick Reference Card

✅ All examples compiled and tested with C++17 (-std=c++17 -O2).