Skip to main content

​
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.
How to Use This Library:
  1. Understand the algorithm first (previous chapters)
  2. Copy the implementation during contests
  3. Modify as needed for the specific problem

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

struct Fenwick {
    int n;
    vector<ll> tree;
    
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, ll delta) {
        for (++i; i <= n; i += i & (-i))
            tree[i] += delta;
    }
    
    ll query(int i) {  // Sum [0, i]
        ll sum = 0;
        for (++i; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }
    
    ll query(int l, int r) {  // Sum [l, r]
        return query(r) - (l > 0 ? query(l - 1) : 0);
    }
};

​
Sparse Table (Static RMQ)

struct SparseTable {
    int n, LOG;
    vector<vector<int>> table;
    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;
        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))]);
    }
    
    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

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.