CP Code Library

Your Contest Arsenal

This chapter contains battle-tested implementations ready for copy-paste in contests. Each snippet is optimized for competitive programming: minimal boilerplate, correct edge case handling, and reliable under contest time pressure.

How to Use This Library:

Understand the algorithm first (previous chapters)
Copy the implementation during contests
Modify as needed for the specific problem
Test locally before submitting — even trusted templates can need adjustments for specific index conventions (0-based vs 1-based) or data types

Common pitfall with library code: Blindly copy-pasting without adapting to the problem’s indexing, data type, or modulus will cause WA. Always double-check: does this problem use 0-indexed or 1-indexed nodes? Is int sufficient or do I need long long? Is the modulus 10^9+7 or 998244353?

Number Theory

GCD, LCM, Extended GCD

// GCD using built-in
ll gcd(ll a, ll b) { return __gcd(a, b); }

// LCM (careful of overflow)
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// Extended Euclidean Algorithm
// Returns gcd(a, b) and finds x, y such that ax + by = gcd(a, b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular inverse using extended GCD (mod must be prime or coprime with a)
ll modinv(ll a, ll mod) {
    ll x, y;
    ll g = extgcd(a, mod, x, y);
    if (g != 1) return -1;  // No inverse
    return (x % mod + mod) % mod;
}

Modular Arithmetic

const ll MOD = 1e9 + 7;

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

// Fast modular exponentiation
ll power(ll base, ll exp, ll mod = MOD) {
    ll 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)
ll modinv(ll a, ll mod = MOD) {
    return power(a, mod - 2, mod);
}

ll divide(ll a, ll b) { return mul(a, modinv(b)); }

Sieve of Eratosthenes

const int MAXN = 1e7 + 5;
bool isPrime[MAXN];
vector<int> primes;

void sieve() {
    fill(isPrime, isPrime + MAXN, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i < MAXN; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (ll j = (ll)i * i; j < MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Linear sieve with smallest prime factor
int spf[MAXN];  // Smallest prime factor

void linearSieve() {
    for (int i = 2; i < MAXN; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || (ll)i * p >= MAXN) break;
            spf[i * p] = p;
        }
    }
}

Prime Factorization

// O(sqrt(n)) factorization
vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> factors;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            factors.push_back({p, cnt});
        }
    }
    if (n > 1) factors.push_back({n, 1});
    return factors;
}

// O(log n) factorization using SPF
vector<pair<int, int>> factorizeFast(int n) {
    vector<pair<int, int>> factors;
    while (n > 1) {
        int p = spf[n], cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        factors.push_back({p, cnt});
    }
    return factors;
}

Combinatorics (nCr with Precomputation)

const int MAXN = 2e5 + 5;
const ll MOD = 1e9 + 7;

ll fact[MAXN], inv_fact[MAXN];

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

ll C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

ll P(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[n-r] % MOD;
}

Data Structures

Disjoint Set Union (DSU)

struct DSU {
    vector<int> parent, rank_, size_;
    int components;
    
    DSU(int n) : parent(n + 1), rank_(n + 1, 0), size_(n + 1, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        size_[px] += size_[py];
        if (rank_[px] == rank_[py]) rank_[px]++;
        components--;
        return true;
    }
    
    bool connected(int x, int y) { return find(x) == find(y); }
    int getSize(int x) { return size_[find(x)]; }
};

Segment Tree (Point Update, Range Query)

template<typename T>
struct SegTree {
    int n;
    vector<T> tree;
    T identity;
    function<T(T, T)> combine;
    
    SegTree(int n, T identity, function<T(T, T)> combine) 
        : n(n), tree(4 * n, identity), identity(identity), combine(combine) {}
    
    SegTree(vector<T>& arr, T identity, function<T(T, T)> combine) 
        : n(arr.size()), tree(4 * n), identity(identity), combine(combine) {
        build(arr, 1, 0, n - 1);
    }
    
    void build(vector<T>& 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] = combine(tree[2 * node], tree[2 * node + 1]);
    }
    
    void update(int idx, T val) { update(1, 0, n - 1, idx, val); }
    
    void update(int node, int start, int end, int idx, T 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] = combine(tree[2 * node], tree[2 * node + 1]);
    }
    
    T query(int l, int r) { return query(1, 0, n - 1, l, r); }
    
    T query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return identity;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return combine(query(2 * node, start, mid, l, r),
                      query(2 * node + 1, mid + 1, end, l, r));
    }
};

// Usage:
// Sum: SegTree<ll> st(n, 0, [](ll a, ll b) { return a + b; });
// Min: SegTree<ll> st(n, LLONG_MAX, [](ll a, ll b) { return min(a, b); });
// Max: SegTree<ll> st(n, LLONG_MIN, [](ll a, ll b) { return max(a, b); });

Lazy Segment Tree (Range Update, Range Query)

struct LazySegTree {
    int n;
    vector<ll> tree, lazy;
    
    LazySegTree(int n) : n(n), tree(4 * n, 0), lazy(4 * n, 0) {}
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void updateRange(int l, int r, ll val) { updateRange(1, 0, n - 1, l, r, val); }
    
    void updateRange(int node, int start, int end, int l, int r, ll val) {
        push(node, start, end);
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        updateRange(2 * node, start, mid, l, r, val);
        updateRange(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    ll query(int l, int r) { return query(1, 0, n - 1, l, r); }
    
    ll query(int node, int start, int end, int l, int r) {
        push(node, start, end);
        if (r < start || end < l) return 0;
        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);
    }
};

Fenwick Tree (BIT)

A Fenwick tree (Binary Indexed Tree) supports point updates and prefix sum queries in O(log n). It uses half the memory of a segment tree and has a much smaller constant factor, making it the preferred choice when you only need prefix sums (no range min/max). When to use Fenwick over Segment Tree: Fenwick is simpler and faster for sum queries. Use a segment tree only when you need range updates (lazy propagation), range min/max, or other non-invertible operations.

struct Fenwick {
    int n;
    vector<ll> tree;
    
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    
    // Add delta to element at position i (0-indexed)
    void update(int i, ll delta) {
        for (++i; i <= n; i += i & (-i))  // i & (-i) isolates the lowest set bit
            tree[i] += delta;
    }
    
    // Query prefix sum [0, i] (0-indexed)
    ll query(int i) {
        ll sum = 0;
        for (++i; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }
    
    // Query range sum [l, r] (0-indexed, inclusive)
    ll query(int l, int r) {
        return query(r) - (l > 0 ? query(l - 1) : 0);
    }
};
// NOTE: This implementation is 0-indexed externally. Internally it converts
// to 1-indexed because Fenwick trees require 1-based indexing to work correctly.
// Edge case: query(0, 0) returns the single element at index 0.

Sparse Table (Static RMQ)

O(n log n) build, O(1) query for idempotent operations (min, max, GCD, OR, AND). Does NOT support updates—use a segment tree if you need updates. Why “idempotent” matters: An operation is idempotent if applying it to overlapping ranges gives the correct answer. For min: min(min(a,b,c), min(b,c,d)) = min(a,b,c,d). For sum, this fails: overlapping ranges would double-count. That is why sparse table gives O(1) for min/max/GCD but not for sum. When to use over segment tree: When there are no updates and you need the fastest possible queries. Sparse table O(1) queries beat segment tree O(log n) queries, which matters when there are 10^6+ queries.

struct SparseTable {
    int n, LOG;
    vector<vector<int>> table;  // table[j][i] = answer for range [i, i + 2^j - 1]
    vector<int> log2_;
    
    SparseTable(vector<int>& arr) : n(arr.size()) {
        LOG = __lg(n) + 1;
        table.assign(LOG, vector<int>(n));
        log2_.resize(n + 1);
        
        for (int i = 2; i <= n; i++)
            log2_[i] = log2_[i / 2] + 1;
        
        table[0] = arr;  // Base: ranges of length 1
        for (int j = 1; j < LOG; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                table[j][i] = min(table[j-1][i], table[j-1][i + (1 << (j-1))]);
    }
    
    // O(1) query: overlap two precomputed ranges that together cover [l, r]
    int query(int l, int r) {
        int k = log2_[r - l + 1];
        return min(table[k][l], table[k][r - (1 << k) + 1]);
    }
};

Trie

struct Trie {
    struct Node {
        int children[26] = {};
        int count = 0;
        int prefixCount = 0;
    };
    
    vector<Node> nodes;
    
    Trie() { nodes.push_back(Node()); }
    
    void insert(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!nodes[cur].children[idx]) {
                nodes[cur].children[idx] = nodes.size();
                nodes.push_back(Node());
            }
            cur = nodes[cur].children[idx];
            nodes[cur].prefixCount++;
        }
        nodes[cur].count++;
    }
    
    int countWord(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!nodes[cur].children[idx]) return 0;
            cur = nodes[cur].children[idx];
        }
        return nodes[cur].count;
    }
    
    int countPrefix(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!nodes[cur].children[idx]) return 0;
            cur = nodes[cur].children[idx];
        }
        return nodes[cur].prefixCount;
    }
};

Graph Algorithms

Dijkstra’s Algorithm

vector<ll> dijkstra(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<ll> dist(n, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

Bellman-Ford

pair<vector<ll>, bool> bellmanFord(int start, int n, 
                                    vector<tuple<int, int, ll>>& edges) {
    vector<ll> dist(n + 1, LLONG_MAX);
    dist[start] = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // Check for negative cycle
    for (auto [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            return {dist, true};  // Has negative cycle
        }
    }
    
    return {dist, false};
}

Floyd-Warshall

void floydWarshall(vector<vector<ll>>& dist) {
    int n = dist.size();
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Topological Sort (Kahn’s Algorithm)

vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> inDegree(n + 1, 0);
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            inDegree[v]++;
    
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (inDegree[i] == 0) q.push(i);
    
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (int v : adj[u])
            if (--inDegree[v] == 0)
                q.push(v);
    }
    
    if (order.size() != n) return {};  // Cycle exists
    return order;
}

LCA (Binary Lifting)

struct LCA {
    int n, LOG;
    vector<vector<int>> up;
    vector<int> depth;
    
    LCA(int n, vector<vector<int>>& adj, int root = 1) : n(n) {
        LOG = __lg(n) + 1;
        up.assign(n + 1, vector<int>(LOG));
        depth.resize(n + 1);
        
        dfs(root, root, adj);
        
        for (int j = 1; j < LOG; j++)
            for (int i = 1; i <= n; i++)
                up[i][j] = up[up[i][j-1]][j-1];
    }
    
    void dfs(int u, int p, vector<vector<int>>& adj) {
        up[u][0] = p;
        for (int v : adj[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u, adj);
            }
        }
    }
    
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        
        for (int j = 0; j < LOG; j++)
            if ((diff >> j) & 1)
                u = up[u][j];
        
        if (u == v) return u;
        
        for (int j = LOG - 1; j >= 0; j--)
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        
        return up[u][0];
    }
    
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
};

Kruskal’s MST

ll kruskal(int n, vector<tuple<ll, int, int>>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    
    ll mstWeight = 0;
    int edgesUsed = 0;
    
    for (auto [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            mstWeight += w;
            if (++edgesUsed == n - 1) break;
        }
    }
    
    return edgesUsed == n - 1 ? mstWeight : -1;  // -1 if not connected
}

String Algorithms

Z-Function

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    
    return z;
}

KMP (Failure Function)

vector<int> computeLPS(const string& pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    
    int len = 0, i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    
    return lps;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> lps = computeLPS(pattern);
    vector<int> matches;
    
    int n = text.size(), m = pattern.size();
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1];
            }
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    
    return matches;
}

String Hashing

struct StringHash {
    const ll MOD = 1e9 + 7, BASE = 31;
    int n;
    vector<ll> hash_, power;
    
    StringHash(const string& s) : n(s.size()), hash_(n + 1), power(n + 1) {
        power[0] = 1;
        for (int i = 0; i < n; i++) {
            hash_[i + 1] = (hash_[i] * BASE + s[i] - 'a' + 1) % MOD;
            power[i + 1] = power[i] * BASE % MOD;
        }
    }
    
    ll getHash(int l, int r) {  // [l, r] inclusive
        return (hash_[r + 1] - hash_[l] * power[r - l + 1] % MOD + MOD) % MOD;
    }
};

Geometry

Point and Vector

struct Point {
    ld x, y;
    
    Point(ld x = 0, ld y = 0) : x(x), y(y) {}
    
    Point operator+(const Point& p) const { return {x + p.x, y + p.y}; }
    Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
    Point operator*(ld t) const { return {x * t, y * t}; }
    Point operator/(ld t) const { return {x / t, y / t}; }
    
    ld dot(const Point& p) const { return x * p.x + y * p.y; }
    ld cross(const Point& p) const { return x * p.y - y * p.x; }
    ld norm() const { return sqrt(x * x + y * y); }
    
    bool operator<(const Point& p) const {
        if (abs(x - p.x) > EPS) return x < p.x;
        return y < p.y;
    }
};

// Cross product of vectors OA and OB
ld cross(Point O, Point A, Point B) {
    return (A - O).cross(B - O);
}

Convex Hull

Andrew’s monotone chain algorithm: Build lower hull left-to-right, then upper hull right-to-left. Uses cross product to determine turn direction: positive = left turn (keep), zero = collinear, negative = right turn (remove last point). Edge cases: If all points are collinear, the “hull” is a line segment. If n < 3, return all points. Duplicate points should be handled by the <= in the cross product check (use < to keep collinear points on the hull boundary).

vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points;
    
    sort(points.begin(), points.end());
    
    vector<Point> hull;
    
    // Build lower hull
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && 
               cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]);
    }
    
    // Build upper hull
    int lower = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lower && 
               cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]);
    }
    
    hull.pop_back();
    return hull;
}

Miscellaneous

Coordinate Compression

template<typename T>
vector<T> compress(vector<T>& arr) {
    vector<T> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    for (auto& x : arr) {
        x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }
    
    return sorted;  // Returns mapping: compressed[i] = original value
}

Random Number Generation

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randint(int lo, int hi) {
    return uniform_int_distribution<int>(lo, hi)(rng);
}

ll randll(ll lo, ll hi) {
    return uniform_int_distribution<ll>(lo, hi)(rng);
}

// Shuffle array randomly
shuffle(arr.begin(), arr.end(), rng);

Custom Comparator for Priority Queue

// Min heap (default is max heap)
priority_queue<int, vector<int>, greater<int>> minHeap;

// Custom comparator
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;  // Min by second element
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

Key Takeaways

Tested Code

All snippets are battle-tested in real contests.

Copy-Paste Ready

Implementations are self-contained and ready to use.

Understand First

Know the algorithm before using the code.

Customize

Modify as needed for your specific problem.

Back to Course Overview

Review the complete course curriculum.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Documentation Index

​CP Code Library

​Your Contest Arsenal

​Number Theory

​GCD, LCM, Extended GCD

​Modular Arithmetic

​Sieve of Eratosthenes

​Prime Factorization

​Combinatorics (nCr with Precomputation)

​Data Structures

​Disjoint Set Union (DSU)

​Segment Tree (Point Update, Range Query)

​Lazy Segment Tree (Range Update, Range Query)

​Fenwick Tree (BIT)

​Sparse Table (Static RMQ)

​Trie

​Graph Algorithms

​Dijkstra’s Algorithm

​Bellman-Ford

​Floyd-Warshall

​Topological Sort (Kahn’s Algorithm)

​LCA (Binary Lifting)

​Kruskal’s MST

​String Algorithms

​Z-Function

​KMP (Failure Function)

​String Hashing

​Geometry

​Point and Vector

​Convex Hull

​Miscellaneous

​Coordinate Compression

​Random Number Generation

​Custom Comparator for Priority Queue

​Key Takeaways

Tested Code

Copy-Paste Ready

Understand First

Customize

Back to Course Overview

CP Code Library

Your Contest Arsenal

Number Theory

GCD, LCM, Extended GCD

Modular Arithmetic

Sieve of Eratosthenes

Prime Factorization

Combinatorics (nCr with Precomputation)

Data Structures

Disjoint Set Union (DSU)

Segment Tree (Point Update, Range Query)

Lazy Segment Tree (Range Update, Range Query)

Fenwick Tree (BIT)

Sparse Table (Static RMQ)

Trie

Graph Algorithms

Dijkstra’s Algorithm

Bellman-Ford

Floyd-Warshall

Topological Sort (Kahn’s Algorithm)

LCA (Binary Lifting)

Kruskal’s MST

String Algorithms

Z-Function

KMP (Failure Function)

String Hashing

Geometry

Point and Vector

Convex Hull

Miscellaneous

Coordinate Compression

Random Number Generation

Custom Comparator for Priority Queue

Key Takeaways