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.

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).