Disjoint Set Union

Data Structure Time: O(α(n)) per op · Space: O(n)

// description

DSU (also called Union-Find) maintains a collection of disjoint sets and supports two operations efficiently: merge two sets, and find the representative (root) of a set.

This implementation uses two classic optimisations:

Path compression — on every rootof call, all nodes on the path are linked directly to the root.
Union by rank — always attach the shorter tree under the taller one to keep trees flat.

Together these give an amortised near-constant O(α(n)) per operation, where α is the inverse Ackermann function (≤ 4 for any practical input size).

Used for: MST (Kruskal), cycle detection, connected components, offline LCA, dynamic connectivity.

// DSU.cpp

#include<bits/stdc++.h>
using namespace std;

struct DSU {
    int n;
    vector<int> parent, rank;

    DSU(int n) : n(n), parent(n), rank(n) {
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

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

    bool merge(int x, int y) {
        int a = rootof(x), b = rootof(y);
        if(a == b) return false; // already same set
        if(rank[a] > rank[b])      parent[b] = a;
        else if(rank[a] < rank[b]) parent[a] = b;
        else { rank[a]++; parent[b] = a; }
        return true;
    }
};

Segment Tree (Lazy Propagation)

Data Structure Time: O(log n) per query/update · Space: O(4n)

// description

A Segment Tree partitions an array into segments stored in a binary tree, enabling range queries and range updates in O(log n).

This version uses lazy propagation: instead of immediately pushing updates to all children, each node stores a pending lazy value that is pushed down only when a node is visited. This turns range updates from O(n) to O(log n).

The implementation here is built on an Euler tour of a tree, using two separate segment trees — one per parity level — to support subtree updates and point queries on trees.

Used for: Range sum/min/max, range add/set, DSU on tree, HLD queries, offline problems.

// Segment Tree.cpp

struct SegTree {
    int lazy[MX * 4];

    void update(int node, int b, int e,
                int i, int j, int val) {
        if(j < b || i > e) return;
        if(i <= b && e <= j) { lazy[node] += val; }
        int lson = node*2, rson = lson+1,
            mid  = (b+e)/2;
        if(lazy[node] && b != e) { // push down
            lazy[lson] += lazy[node];
            lazy[rson] += lazy[node];
            lazy[node]  = 0;
        }
        if(i <= b && e <= j) return;
        update(lson, b, mid, i, j, val);
        update(rson, mid+1, e, i, j, val);
    }

    int query(int node, int b, int e, int i) {
        if(i < b || i > e) return 0;
        int lson = node*2, rson = lson+1,
            mid  = (b+e)/2;
        if(lazy[node] && b != e) { // push down
            lazy[lson] += lazy[node];
            lazy[rson] += lazy[node];
            lazy[node]  = 0;
        }
        if(b == e) return lazy[node];
        return query(lson, b, mid, i)
             + query(rson, mid+1, e, i);
    }
};

Heavy-Light Decomposition

Tree Time: O(log²n) per path query · Space: O(n log n)

// description

HLD decomposes a tree into a set of vertex-disjoint chains by always extending a chain through the child with the largest subtree (the "heavy" child). Any root-to-leaf path crosses at most O(log n) chains.

Each chain is a contiguous segment in a flattened DFS order, so any path query becomes a series of range queries on a Segment Tree — one per chain boundary crossed.

This implementation:

Uses get_sz to compute subtree sizes and parent pointers.
Builds chains via hld() assigning new DFS names.
Embeds a sparse-table LCA for path queries between arbitrary nodes.
Uses a max Segment Tree to answer "max edge weight on path u→v".

Used for: Path sum/max/min on trees, edge/node updates on paths, subtree queries combined with path queries.

// hld.cpp (core)

void get_sz(int u, int p) {
    sz[u] = 1;
    for(int v : edge[u]) if(v != p) {
        par[v] = u; lev[v] = lev[u]+1;
        get_sz(v, u);
        sz[u] += sz[v];
    }
}

void hld(int u, int p, bool isHead) {
    newName[u] = ++Name;
    if(isHead) chain++, chainHead[chain] = u;
    chainNo[u] = chain;
    int bigChild = 0, mxi = -1;
    for(int v : edge[u])
        if(v != p && sz[v] > mxi)
            mxi = sz[v], bigChild = v;
    if(bigChild) hld(bigChild, u, 0); // extend chain
    for(int v : edge[u])
        if(v != p && v != bigChild)
            hld(v, u, 1); // start new chain
}

int query_up(int u, int v) {
    int ret = 0;
    while(1) {
        if(chainNo[u] == chainNo[v]) {
            ret = max(ret, query(1,1,n,newName[v]+1,newName[u]));
            break;
        }
        ret = max(ret, query(1,1,n,
              newName[chainHead[chainNo[u]]], newName[u]));
        u = par[chainHead[chainNo[u]]];
    }
    return ret;
}

Lowest Common Ancestor

Tree Build: O(n log n) · Query: O(log n)

// description

LCA finds the deepest node that is an ancestor of both u and v. This implementation uses binary lifting: for each node, precompute ancestors at distances 1, 2, 4, 8… (powers of two) in a sparse table.

To answer a query:

Lift the deeper node until both are at the same depth.
Simultaneously lift both until their ancestors diverge.
The parent of either is the LCA.

The sparse table is built in O(n log n) with a standard DP: sp[v][j] = sp[sp[v][j-1]][j-1].

Used for: Tree path queries, HLD preprocessing, distance between nodes, offline RMQ, cycle detection in directed graphs.

// lowest Common Anccestor.cpp

int sp[MX][23], L[MX];

// build sparse table after DFS
for(int j = 1; (1<<j) <= n; j++)
    for(int i = 1; i <= n; i++)
        if(sp[i][j-1] != -1)
            sp[i][j] = sp[sp[i][j-1]][j-1];

int findlca(int u, int v) {
    if(L[u] < L[v]) swap(u, v);
    int diff = L[u] - L[v];
    for(int i = 22; i >= 0; i--)
        if(diff & (1 << i))
            u = sp[u][i]; // lift u to same depth
    if(u == v) return u;
    for(int i = 22; i >= 0; i--)
        if(sp[u][i] != sp[v][i])
            u = sp[u][i], v = sp[v][i];
    return sp[u][0]; // parent is LCA
}

KMP — Knuth-Morris-Pratt

String Time: O(n + m) · Space: O(m)

// description

KMP finds all occurrences of a pattern P in a text T in linear time by avoiding redundant comparisons using the failure function (LPS array).

The failure function lps[i] stores the length of the longest proper prefix of P[0..i] that is also a suffix. When a mismatch occurs at position i, instead of restarting from scratch, we jump to lps[i-1] — the longest border — and continue matching.

This implementation builds the LPS array directly as a 1-indexed char array.

Used for: Pattern matching, counting occurrences, period of a string, string border detection, Aho-Corasick backbone.

// kmp.cpp

char a[MX];
int  lps[MX];

// build failure function (1-indexed)
int cur = 1;
lps[0] = -1;
lps[1] =  0;

for(int i = 2; i <= n; i++) {
    while(cur != 0 && a[cur] != a[i])
        cur = lps[cur - 1] + 1; // fall back
    lps[i] = cur++;
}

// lps[i] = length of longest proper
// prefix of a[1..i] that is also suffix

Z Algorithm

String Time: O(n) · Space: O(n)

// description

The Z-function of a string S is an array where z[i] is the length of the longest substring starting at S[i] that is also a prefix of S.

The algorithm maintains a window [l, r] — the rightmost Z-box seen so far. For each new position i:

If i ≤ r, initialise z[i] from the already-known value z[i-l] (capped at r−i+1).
Then extend naively while characters match.

Each character is visited at most twice, giving O(n) total.

Used for: Pattern matching (concatenate pattern#text), string periods, palindrome detection, string equality queries.

// z algo.cpp

// zero-indexed
vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n);
    for(int i = 1, l = 0, r = 0; i < n; i++) {
        if(i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        while(i + z[i] < n &&
              s[z[i]] == s[i + z[i]])
            ++z[i];
        if(i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

Mo's Algorithm

Offline Time: O((n + q)√n) · Space: O(n + q)

// description

Mo's algorithm answers offline range queries efficiently by sorting them in a specific order that minimises the total movement of two pointers [l, r].

Queries are sorted by block of left endpoint (block size √n), then by right endpoint within each block. This ensures:

Total movement of r: O(n√n)
Total movement of l: O(q√n)

This implementation solves XOR range queries — maintaining a count array and a running answer that updates in O(1) per pointer move.

Used for: Range frequency, range XOR, range distinct count, any problem where add/remove is O(1) but rebuild is expensive.

// Mo's Algorithm.cpp

int SQ;
struct Query {
    int l, r, idx;
    bool operator<(const Query &a) const {
        if(l/SQ == a.l/SQ) return r < a.r;
        return l/SQ < a.l/SQ;
    }
} Q[MX];

int  cnt[7000005];
long long counti = 0;

inline void add(int i) {
    counti += cnt[ara[i] ^ k];
    cnt[ara[i]]++;
}
inline void rem(int i) {
    cnt[ara[i]]--;
    counti -= cnt[ara[i] ^ k];
}

// process queries
SQ = sqrt(n);
sort(Q, Q+m);
int L = 0, R = 0;
for(int i = 0; i < m; i++) {
    while(L < Q[i].l) rem(L++);
    while(L > Q[i].l) add(--L);
    while(R < Q[i].r) add(++R);
    while(R > Q[i].r) rem(R--);
    ans[Q[i].idx] = counti;
}

Fast Fourier Transform

Math Time: O(n log n) · Space: O(n)

// description

FFT evaluates a polynomial at n roots of unity in O(n log n) using the Cooley-Tukey divide-and-conquer algorithm. Polynomial multiplication then becomes: FFT both, pointwise multiply, inverse FFT.

The key idea: a degree-n polynomial can be split into its even- and odd-indexed coefficients, each of degree n/2. Evaluating both halves recursively and combining takes O(n) per level over O(log n) levels.

The invert flag triggers the inverse FFT (conjugate twiddle factors + divide by n) to convert back from value representation to coefficient representation.

Used for: Polynomial multiplication, large integer multiplication, convolution, string matching over alphabets, counting problems reducible to convolution.

// FFT(without modulo).cpp

typedef complex<long double> base;

void fft(vector<base> &a, bool invert) {
    int n = a.size();
    // bit-reversal permutation
    for(int i=1,j=0; i<n; i++) {
        int bit = n>>1;
        for(; j>=bit; bit>>=1) j-=bit;
        j += bit;
        if(i < j) swap(a[i], a[j]);
    }
    for(int len=2; len<=n; len<<=1) {
        long double ang = 2*pi/len*(invert?-1:1);
        base wlen(cos(ang), sin(ang));
        for(int i=0; i<n; i+=len) {
            base w(1);
            for(int j=0; j<len/2; j++) {
                base u = a[i+j];
                base v = a[i+j+len/2] * w;
                a[i+j]        = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if(invert)
        for(int i=0; i<n; i++) a[i] /= n;
}

Convex Hull

Geometry Time: O(n log n) · Space: O(n)

// description

Finds the smallest convex polygon containing all given points. This is Andrew's monotone chain algorithm.

After sorting points lexicographically (by x, then y), the algorithm builds the lower and upper hulls separately by scanning left-to-right and right-to-left, maintaining the invariant that the hull always makes left turns.

The cross function computes the 2D cross product of vectors OA and OB:

> 0: left turn (keep)
= 0: collinear (remove for strict hull)
< 0: right turn (pop and retry)

Used for: Farthest pair of points, rotating calipers, minimum enclosing rectangle, half-plane intersection, CHT (Convex Hull Trick) for DP optimisation.

// Convex Hull.cpp

struct PT {
    ll x, y;
    bool operator<(PT p) const {
        return x < p.x || (x==p.x && y<p.y);
    }
};

ll cross(PT O, PT A, PT B) {
    return (A.x-O.x)*(B.y-O.y)
         - (A.y-O.y)*(B.x-O.x);
}

vector<PT> convex_hull(vector<PT> P) {
    int n = P.size(), k = 0;
    vector<PT> H(2*n);
    sort(P.begin(), P.end());

    // lower hull
    for(int i = 0; i < n; i++) {
        while(k >= 2 &&
              cross(H[k-2],H[k-1],P[i]) <= 0)
            k--;
        H[k++] = P[i];
    }
    // upper hull
    for(int i = n-2, t = k+1; i >= 0; i--) {
        while(k >= t &&
              cross(H[k-2],H[k-1],P[i]) <= 0)
            k--;
        H[k++] = P[i];
    }
    H.resize(k-1);
    return H;
}