Advanced Data Structures & Algorithms

A Fenwick tree (BIT) is a compact array-based structure that supports point updates and prefix-sum queries in O(log n) time with O(n) space, beating the naive O(n) per query. Each index i stores the sum of a specific range determined by the lowest set bit of i. Query: sum(i) = tree[i] + tree[i - lowbit(i)] + ...; Update: propagate by adding lowbit(i) repeatedly. While less flexible than a segment tree (limited to invertible operations like sum/XOR, not min/max), it has a smaller constant factor and simpler code, making it preferred for competitive programming sum/difference queries.

class BIT:
    def __init__(self, n): self.n=n; self.tree=[0]*(n+1)
    def update(self, i, delta):
        while i<=self.n: self.tree[i]+=delta; i+=i&(-i)
    def query(self, i):
        s=0
        while i>0: s+=self.tree[i]; i-=i&(-i)
        return s
    def range_query(self,l,r): return self.query(r)-self.query(l-1)

Without lazy propagation, a range update (add delta to all elements in [l, r]) would require visiting all O(n) leaves in the range. Lazy propagation defers updates by storing a 'pending' tag at each node. When a range update covers a node's range completely, store the delta in the node's lazy tag rather than propagating further. When querying or partially visiting a node, 'push down' its lazy tag to its children first. This ensures each operation visits at most O(log n) nodes, maintaining O(log n) per query and update while supporting range add, range multiply, range set, and range sum queries simultaneously.

Each insert operation traverses at most L nodes, creating new ones as needed: O(L) per insert, O(n·L) total. Each search is O(L). Space depends on character overlap between words; worst case O(n·L·alphabet_size) for no shared prefixes. In practice, shared prefixes reduce space significantly. A compressed trie (Patricia/Radix tree) merges single-child chains, reducing space to O(n) nodes. Tries support prefix search and autocomplete in O(L), outperforming hash maps (O(L) per lookup but no prefix queries) and sorted arrays (O(L·log n) binary search). Used in spell checkers, IP routing, and word search problems.

AVL trees maintain a balance factor (left height - right height) in {-1, 0, 1} at every node via rotations after insertions/deletions. Four rotation cases: (1) Left-Left (right rotation): heavy subtree is left child's left side; rotate right at the unbalanced node. (2) Right-Right (left rotation): mirror of LL. (3) Left-Right (double rotation): left rotate at left child, then right rotate at node. (4) Right-Left (double rotation): right rotate at right child, then left rotate at node. After each rotation, heights of affected nodes are updated in O(1). All operations remain O(log n) guaranteed, unlike unbalanced BSTs which degrade to O(n).

Red-Black trees guarantee the longest path is at most twice the shortest (not strictly balanced), giving O(log n) worst-case height. AVL trees enforce |left_height - right_height| ≤ 1, achieving ≈ 1.44 log₂ n height—stricter balance. In practice, RB trees require fewer rotations on insertion/deletion (at most 2), making writes faster; AVL trees have better read performance due to lower height. RB trees are used in language standard libraries (Java TreeMap, C++ std::map, Linux CFS scheduler). AVL trees are preferred in read-heavy in-memory databases. Both guarantee O(log n) for all operations.

A skip list is a probabilistic data structure layering multiple sorted linked lists. The bottom layer contains all elements; each higher layer contains a random subset (each element promoted with probability p=0.5). Search starts at the top layer, moving forward until the next element exceeds the target, then dropping down to the next layer. With O(log n) layers on average, search traverses O(log n) nodes. Insert and delete are also O(log n) expected. Skip lists offer the same expected complexity as balanced BSTs with simpler implementation and better concurrent access properties, used in Redis sorted sets.

A Bloom filter is a space-efficient probabilistic set data structure. Insert: hash the element with k independent hash functions, set those k bits in a bit array to 1. Query: check if all k bits are set; if any is 0, the element is definitely not in the set; if all are 1, the element is probably in the set (false positives possible). False positive probability is approximately (1 - e^(-kn/m))^k where n is elements inserted and m is bit array size. Critically, false negatives are impossible—if an element was inserted, all its bits are set. Deletions are not supported in the basic version.

Bellman-Ford relaxes all edges V-1 times, where each round guarantees shortest paths using at most one more edge. After V-1 rounds, all shortest paths (which can have at most V-1 edges in a graph with no negative cycles) are found. A V-th round of relaxation that still finds improvements indicates a negative cycle. Unlike Dijkstra, Bellman-Ford handles negative edge weights correctly because it does not greedily finalize distances. Time is O(V·E) vs Dijkstra's O((V+E) log V). Bellman-Ford is used in routing protocols (BGP, RIP) and as a subroutine in Johnson's algorithm for all-pairs shortest paths.

def bellman_ford(n, edges, src):
    dist = [float('inf')]*n; dist[src]=0
    for _ in range(n-1):
        for u,v,w in edges:
            if dist[u]+w < dist[v]: dist[v]=dist[u]+w
    for u,v,w in edges:
        if dist[u]+w < dist[v]: return None  # negative cycle
    return dist

Floyd-Warshall computes all-pairs shortest paths in a weighted graph in O(V³) time and O(V²) space. It uses DP: dp[i][j][k] = shortest path from i to j using only vertices {1,...,k} as intermediates. The recurrence is dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]), meaning try routing through vertex k or not. In practice, optimize to a 2D table updated in-place. After all iterations, dp[i][i] < 0 indicates vertex i is on a negative cycle. It handles negative edges (but not negative cycles) and is simpler than running Bellman-Ford from each source.

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k]+dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k]+dist[k][j]
    return dist

A* is an informed search algorithm using a heuristic function h(n) estimating the cost from node n to the goal. It prioritizes nodes by f(n) = g(n) + h(n), where g(n) is the actual cost from source to n. If h is admissible (never overestimates the true cost) and consistent (h(n) ≤ cost(n→n') + h(n')), A* guarantees optimal shortest paths. It explores fewer nodes than Dijkstra (which uses h=0) by directing the search toward the goal. Common heuristics: Manhattan distance for grids (4-directional), Euclidean distance for geometric graphs. Used in game AI pathfinding and navigation systems.

import heapq
def a_star(graph, src, dst, h):
    heap = [(h(src), 0, src)]
    dist = {src: 0}
    while heap:
        _, g, u = heapq.heappop(heap)
        if u == dst: return g
        for v, w in graph[u]:
            ng = g + w
            if v not in dist or ng < dist[v]:
                dist[v] = ng
                heapq.heappush(heap, (ng+h(v), ng, v))
    return -1

Kruskal's builds a Minimum Spanning Tree by sorting all edges by weight and greedily adding edges that do not form a cycle (checked via Union-Find). Correctness follows from the cut property: for any cut of the graph (partition into two sets), the minimum weight edge crossing the cut is in some MST. When Kruskal adds an edge, it is the cheapest edge crossing the cut defined by the two components it connects, satisfying the cut property. Sort: O(E log E). Union-Find operations: O(E α(V)). Total: O(E log E). Works on disconnected graphs (produces minimum spanning forest). Preferred over Prim's for sparse graphs.

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    parent = list(range(n))
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    mst, cost = [], 0
    for u,v,w in edges:
        pu,pv=find(u),find(v)
        if pu!=pv:
            parent[pu]=pv; mst.append((u,v,w)); cost+=w
    return cost, mst

Prim's builds an MST by starting from an arbitrary vertex and greedily adding the minimum-weight edge connecting the MST to an unvisited vertex. Use a min-heap: push all edges from the current MST frontier, pop the minimum, and if the destination is unvisited, add it to MST and push its edges. With adjacency lists and a binary heap: O(E log V). With a Fibonacci heap: O(E + V log V). Prim's is preferred for dense graphs (O(V²) with arrays outperforms Kruskal's O(E log E) when E ≈ V²) and when the graph is given as an adjacency matrix. Kruskal's is better for sparse graphs and when edges are pre-sorted.

import heapq
def prim(n, adj):
    visited = set(); cost = 0
    heap = [(0, 0)]
    while heap and len(visited) < n:
        w, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u); cost += w
        for v, wt in adj[u]:
            if v not in visited: heapq.heappush(heap, (wt, v))
    return cost

Knuth-Morris-Pratt searches for pattern P (length m) in text T (length n) in O(n+m) by preprocessing P into a failure function (also called lps: longest proper prefix which is also suffix). lps[i] is the length of the longest proper prefix of P[0..i] that is also a suffix. During search, on a mismatch at position j in P, instead of restarting, jump to lps[j-1] in P—reusing the matched prefix. This avoids redundant comparisons. Preprocessing lps is O(m) using a two-pointer technique. The total number of character comparisons across the full search is O(n+m) since the pattern pointer never goes backward in the text.

def kmp_search(text, pat):
    n,m=len(text),len(pat)
    lps=[0]*m; j=0
    i=1
    while i<m:
        if pat[i]==pat[j]: j+=1; lps[i]=j; i+=1
        elif j: j=lps[j-1]
        else: i+=1
    res=[]; j=0
    for i,c in enumerate(text):
        while j and c!=pat[j]: j=lps[j-1]
        if c==pat[j]: j+=1
        if j==m: res.append(i-m+1); j=lps[j-1]
    return res

Rabin-Karp computes a hash of the pattern and uses a rolling hash over the text window of the same length. Rolling hash updates in O(1): subtract the contribution of the leaving character and add the entering character, multiplied by the appropriate power of the base. Hash match triggers a character-by-character verification to eliminate collisions. For single pattern, average O(n+m) time but O(n·m) worst case (many spurious matches). The key advantage is multi-pattern search: hash all k patterns into a set, then for each text window check if its hash is in the set—O(n+m_total) average, matching k patterns simultaneously without running KMP k times.

def rabin_karp(text, pat, base=31, mod=10**9+7):
    n,m=len(text),len(pat)
    pow_m=pow(base,m,mod)
    def h(s): return sum(ord(c)*pow(base,i,mod) for i,c in enumerate(s))%mod
    ph,wh=h(pat),h(text[:m])
    res=[]
    for i in range(n-m+1):
        if wh==ph and text[i:i+m]==pat: res.append(i)
        if i<n-m:
            wh=(wh-(ord(text[i])*pow(base,i,mod))%mod+mod)*base%mod
            wh=(wh+ord(text[i+m])*pow(base,i+m,mod))%mod
    return res

The Z-array Z[i] stores the length of the longest substring starting at position i that is also a prefix of the string. Computing Z: maintain a window [l, r] of the rightmost Z-box (substring known to match a prefix). For each i, if i < r, initialize Z[i] = min(r-i, Z[i-l]) using previously computed values. Then extend Z[i] by comparing characters beyond r. Update [l, r] if i + Z[i] - 1 > r. Total time is O(n). For string matching, concatenate pattern + '$' + text, compute Z; positions where Z[i] ≥ len(pattern) are match locations. The '$' separator ensures the Z value doesn't extend into the text for false matches.

def z_function(s):
    n=len(s); Z=[0]*n; Z[0]=n; l=r=0
    for i in range(1,n):
        if i<r: Z[i]=min(r-i, Z[i-l])
        while i+Z[i]<n and s[Z[i]]==s[i+Z[i]]: Z[i]+=1
        if i+Z[i]-1>=r: l,r=i,i+Z[i]-1
    return Z

A suffix array SA is an array of indices of all suffixes of a string sorted lexicographically. Combined with the Longest Common Prefix (LCP) array, where LCP[i] is the length of the longest common prefix between SA[i-1] and SA[i] suffixes, it enables powerful string processing. Building SA: O(n log² n) naively, O(n log n) with radix sort, O(n) with SA-IS. Applications: find longest repeated substring (max of LCP array), count distinct substrings (n(n+1)/2 - sum of LCP), string search in O(m log n). Suffix arrays are space-efficient alternatives to suffix trees, using O(n) space vs O(n) with higher constants for suffix trees.

Aho-Corasick searches text of length n for all occurrences of k patterns with total length m_total, reporting z total matches, all in O(n + m_total + z) time. It builds a Trie of all patterns, then computes failure links (analogous to KMP's failure function) across the Trie using BFS. Failure links point to the longest proper suffix of the current node's string that is also a prefix of some pattern in the Trie. Dictionary links point to the nearest ancestor via failure links that is a complete pattern. During text traversal, at each character follow the Trie edge (or failure link on mismatch) and follow dictionary links to report all matching patterns at each position.

Standard DSU with path compression cannot be rolled back because path compression permanently alters structure. DSU with rollback uses union by rank only (no path compression) and maintains a stack of (node, old_parent, old_rank) records. To rollback a union, pop the stack and restore the saved values. Find is O(log n) without path compression. Rollback DSU enables offline dynamic connectivity: process edge insertions and deletions using a divide-and-conquer on time segments. At each time segment, add edges present throughout, answer queries, then rollback. Used in offline dynamic connectivity in O(Q log Q log V) overall, supporting deletions that standard online DSU cannot handle.

A B-tree of order t stores 2t-1 to t-1 keys per node (except root) and has t to 2t children. All leaves are at the same depth. B-trees are designed to minimize disk I/O: each node maps to one disk page, and since each node holds many keys, the tree height is O(log_t n)—drastically smaller than binary trees. With t=500, a B-tree with 10^9 records has height ≈ 5. Database systems (PostgreSQL, MySQL InnoDB) use B+ trees (variant with data only at leaves, linked leaf list for range scans). Binary trees have O(log₂ n) height—impractical when each node access costs a disk read.

Ford-Fulkerson computes maximum flow in a flow network by repeatedly finding augmenting paths (paths from source to sink with available capacity) in the residual graph and pushing flow along them. Each augmentation increases total flow. The algorithm terminates when no augmenting path exists. Max-flow min-cut theorem: the maximum flow equals the minimum capacity cut (partition of vertices into S containing source and T containing sink; cut capacity = sum of capacities of edges from S to T). Edmonds-Karp variant uses BFS for augmenting paths, giving O(V·E²) time. Applications: network routing, bipartite matching (via flow reduction), airline scheduling.

from collections import deque
def bfs_path(graph, s, t, parent):
    visited={s}
    q=deque([s])
    while q:
        u=q.popleft()
        for v in graph[u]:
            if v not in visited and graph[u][v]>0:
                visited.add(v); parent[v]=u; q.append(v)
                if v==t: return True
    return False

A van Emde Boas (vEB) tree supports predecessor, successor, insert, delete, findMin, and findMax on integers in universe {0,...,U-1} in O(log log U) time—faster than O(log n) comparison-based structures when U is fixed. It recursively divides the universe into sqrt(U) clusters of size sqrt(U), with a summary structure tracking which clusters are non-empty. All operations recurse on structures of size sqrt(U), giving the recurrence T(U) = T(sqrt(U)) + O(1), solving to O(log log U). Space is O(U). Practical for integer keys with bounded universe; used in network routing and priority queues with fixed integer keys.

A Treap is a BST where each node has a key and a randomly assigned priority. The tree satisfies the BST property on keys and the max-heap property on priorities. Random priorities ensure the tree is balanced with O(log n) expected height, same as a random BST. Operations: insert adds a node as a leaf, then rotates up to restore heap property on priorities. Delete rotates the node down until it becomes a leaf, then removes it. Split and merge operations make Treaps efficient for range operations. Treaps offer O(log n) expected time for all operations with simple implementation and are used in competitive programming for implicit treaps (sequence data structure).

The Hungarian algorithm solves the assignment problem: given an n×n cost matrix, find a perfect matching between n workers and n jobs minimizing total cost. It works in O(n³) time. The algorithm operates on augmenting paths in a bipartite graph where nodes are connected when a job-worker pair can be in the optimal matching. It maintains a feasible labeling (potentials) and finds augmenting paths via DFS/BFS, adjusting potentials when no augmenting path exists. The solution is guaranteed optimal by the complementary slackness conditions of the LP dual. Applications: job scheduling, optimal assignment, and tracking in computer vision.

Johnson's algorithm runs in O(V·E log V) vs Floyd-Warshall's O(V³), making it better for sparse graphs where E << V². Steps: (1) Add a virtual vertex q with zero-weight edges to all vertices. (2) Run Bellman-Ford from q to find potentials h(v) (shortest path from q to v). If Bellman-Ford detects a negative cycle, no solution exists. (3) Reweight edges: w'(u,v) = w(u,v) + h(u) - h(v) ≥ 0 (guaranteed non-negative). (4) Run Dijkstra from each vertex using reweighted edges. (5) Correct distances: d(u,v) = d'(u,v) + h(v) - h(u). The reweighting preserves relative distances while enabling Dijkstra on originally-negative graphs.

A Cartesian tree is a BST derived from an array where the root is the minimum element, the left subtree is built from elements left of the minimum, and the right subtree from elements right of it—satisfying both BST (inorder = original array) and min-heap properties simultaneously. O(n) construction using a monotonic stack: process elements left to right, maintaining a stack of nodes in increasing order. For each new element, pop nodes greater than it (they become its left subtree), then make the new node the right child of the new stack top, and push the new node. Cartesian trees underlie treaps and enable O(1) LCA with O(n) preprocessing via Euler tour + sparse table.

LCA(u, v) is the deepest node that is an ancestor of both u and v in a rooted tree. Binary lifting preprocesses ancestors: up[v][j] = 2^j-th ancestor of v. Build up table in O(n log n) via DP: up[v][0] = parent[v]; up[v][j] = up[up[v][j-1]][j-1]. For LCA query: first bring u and v to the same depth by lifting the deeper one using binary lifting in O(log n). Then binary lift both together until their ancestors diverge; their parent is the LCA. Each query is O(log n). Total: O(n log n) preprocessing + O(log n) per query. Euler tour + sparse table (range min) gives O(1) queries after O(n log n) preprocessing.

Heavy-light decomposition (HLD) partitions a tree's edges into O(log n) chains by always following the 'heavy child' (child with the largest subtree). Any root-to-leaf path crosses at most O(log n) chains. By mapping chains to contiguous segments in a segment tree array, path queries (sum, max, LCA-based) on tree paths can be answered in O(log² n) per query—O(log n) chains, each queried in O(log n) via the segment tree. This enables: path sum/max updates, subtree sum updates, and LCA-based queries. Alternative: Euler tour + segment tree for subtree queries. HLD is the standard tool for path queries on trees in competitive programming.

The Sieve of Eratosthenes finds all primes up to n. Start with a boolean array is_prime of size n+1, initialized to True. Mark 0 and 1 as not prime. For each p from 2 to sqrt(n), if is_prime[p] is True, mark all multiples of p starting from p² as False. Primes are the indices remaining True. Time complexity is O(n log log n) due to the harmonic series of prime reciprocals: the total markings are n/2 + n/3 + n/5 + ... ≈ n ln ln n. Space is O(n). Segmented sieve reduces space to O(sqrt(n)) for generating primes in a range [l, r]. Linear sieve achieves O(n) by marking each composite exactly once.

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0]=is_prime[1]=False
    p=2
    while p*p<=n:
        if is_prime[p]:
            for i in range(p*p, n+1, p):
                is_prime[i]=False
        p+=1
    return [i for i,v in enumerate(is_prime) if v]

Binary exponentiation computes a^b mod m by repeatedly squaring: if b is even, a^b = (a^(b/2))². If b is odd, a^b = a · a^(b-1). This halves the exponent each step, giving O(log b) multiplications. Each multiplication takes O(1) with mod m. The iterative version uses bit manipulation: if the current bit of b is set, multiply result by the current power of a; square a and shift b right. This replaces O(b) naïve multiplications. Applications: RSA cryptography, modular inverse (Fermat's little theorem: a^(m-2) mod m for prime m), and competitive programming number theory problems.

def pow_mod(a, b, m):
    result = 1; a %= m
    while b > 0:
        if b & 1: result = result*a%m
        a = a*a%m; b >>= 1
    return result

Sparse table answers static range minimum (or maximum) queries in O(1) after O(n log n) preprocessing. Build: table[i][j] = min of 2^j elements starting at index i, computed via DP: table[i][j] = min(table[i][j-1], table[i + 2^(j-1)][j-1]). For a range [l, r] query, find k = floor(log₂(r-l+1)); answer = min(table[l][k], table[r-2^k+1][k]). Since min is idempotent (min of overlapping ranges is still correct), overlapping intervals are allowed. Space is O(n log n). Unlike segment trees, sparse tables cannot handle updates. Used for offline range minimum queries and LCA via Euler tour.

import math
def build_sparse(arr):
    n=len(arr); LOG=n.bit_length()
    sp=[[0]*n for _ in range(LOG)]
    sp[0]=arr[:]
    for j in range(1,LOG):
        for i in range(n-(1<<j)+1):
            sp[j][i]=min(sp[j-1][i],sp[j-1][i+(1<<(j-1))])
    def rmq(l,r):
        k=int(math.log2(r-l+1))
        return min(sp[k][l],sp[k][r-(1<<k)+1])
    return rmq

Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time and O(1) space. Maintain two variables: current_sum (max sum ending at the current index) and max_sum (overall maximum seen). For each element x: current_sum = max(x, current_sum + x)—either start a new subarray at x or extend the current one. Update max_sum = max(max_sum, current_sum). The key insight: if current_sum becomes negative, starting fresh from the next element is always better. To track the subarray indices, record start and end positions whenever max_sum is updated, and reset the start index when a new subarray begins.

def kadane(nums):
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

A persistent data structure preserves previous versions after updates. A persistent segment tree shares unchanged nodes across versions. On update, only O(log n) new nodes are created (the path from root to the updated leaf); all other nodes are shared with the previous version. Each version has its own root pointer. This requires O(n + Q log n) space for n elements and Q updates, vs O(n) for a non-persistent segment tree. Queries on any historical version simply use that version's root. Applications: range queries on historical data, offline K-th smallest in range (merge sort tree alternative), and version control for data.

Quickselect partitions the array around a pivot (like quicksort) but recurses only on the side containing the k-th element. Choose a pivot (randomly for O(n) average), partition into elements ≤ pivot and > pivot. If the pivot lands at position k, return it. If k < pivot_index, recurse left; else recurse right with adjusted k. Average case: T(n) = T(n/2) + O(n) solving to O(n). Worst case with bad pivot: O(n²). Median-of-medians guarantees O(n) worst case by choosing a pivot within 30-70% of the array. In Python, use random.choice for pivot to achieve expected O(n).

import random
def quickselect(arr, k):
    if len(arr)==1: return arr[0]
    pivot=random.choice(arr)
    lo=[x for x in arr if x<pivot]
    mid=[x for x in arr if x==pivot]
    hi=[x for x in arr if x>pivot]
    if k<len(lo): return quickselect(lo,k)
    elif k<len(lo)+len(mid): return pivot
    else: return quickselect(hi,k-len(lo)-len(mid))

Counting sort counts occurrences of each distinct element (assuming integer keys in range [0, k]), computes prefix sums to determine positions, then places each element in the output array. Time is O(n + k); space is O(n + k). It beats O(n log n) comparison sorts when k = O(n), i.e., the key range is proportional to the number of elements. Counting sort is stable (preserves relative order of equal elements), making it the inner sort for radix sort. Radix sort applies counting sort digit by digit (LSD to MSD), sorting n integers of d digits in O(d·(n+k)) total—effectively O(n) when digits and digit range are constants.

def counting_sort(arr, k):
    count=[0]*(k+1)
    for n in arr: count[n]+=1
    for i in range(1,k+1): count[i]+=count[i-1]
    out=[0]*len(arr)
    for n in reversed(arr):
        count[n]-=1; out[count[n]]=n
    return out

2-SAT determines satisfiability of a conjunction of clauses, each a disjunction of at most 2 Boolean literals. Model each variable x as two nodes x and ¬x. Each clause (a ∨ b) adds implications ¬a→b and ¬b→a. The formula is satisfiable if and only if for no variable x are x and ¬x in the same Strongly Connected Component (SCC) of the implication graph. Solve with Kosaraju's or Tarjan's SCC algorithm in O(V + E). Assign each variable by comparing SCC indices: if SCC(x) > SCC(¬x) (topological order), x is True. 2-SAT is solvable in polynomial time; 3-SAT is NP-complete.

Tarjan's algorithm finds Strongly Connected Components (SCCs) in a directed graph with a single DFS. Each node gets a discovery time and a low-link value (earliest discovery time reachable via DFS tree and one back edge). Nodes are pushed onto a stack when visited. When a node's low-link equals its discovery time, it is an SCC root; pop all stack nodes up to and including it—that set is one SCC. The low-link value propagates upward through tree edges and back edges but not cross edges (distinguished by whether the neighbor is on the stack). All V nodes and E edges are processed exactly once: O(V + E).

A Palindromic Tree (Eertree) is an implicit structure that represents all distinct palindromic substrings of a string in O(n) space. It has at most n+2 nodes (at most n distinct palindromic substrings plus two root nodes for odd-length and even-length seeds). Each node represents a unique palindromic substring with its length and suffix link (pointing to the longest proper palindromic suffix). Built online in O(n) total time by processing each character and following suffix links to find where to attach the new palindrome. Useful for palindrome counting, longest palindromic suffix at each position, and palindrome series problems in competitive programming.

Manacher's algorithm computes P[i] = radius of the longest palindrome centered at i in the transformed string (with '#' separators, making all palindromes odd-length). Maintain the rightmost palindrome boundary (r) and its center (c). For each i ≤ r, initialize P[i] = min(r-i, P[2c-i]) using the mirror. Then expand while characters match. Update (c, r) if i+P[i] > r. This reuse of previously computed palindrome extents ensures each character is processed at most twice, giving O(n). The result: P[i]/2 in the original string gives the radius of palindromes at each position. All O(n) distinct palindrome lengths are computed simultaneously.

def manacher(s):
    t='#'+'#'.join(s)+'#'
    n=len(t); P=[0]*n; c=r=0
    for i in range(n):
        if i<r: P[i]=min(r-i, P[2*c-i])
        while i-P[i]-1>=0 and i+P[i]+1<n and t[i-P[i]-1]==t[i+P[i]+1]:
            P[i]+=1
        if i+P[i]>r: c,r=i,i+P[i]
    return P

The Convex Hull Trick reduces DP transitions of the form dp[i] = min(dp[j] + b[j]·a[i]) from O(n²) to O(n) or O(n log n). It applies when the transition cost decomposes into a product of a function of j (slope b[j]) and a function of i (query point a[i]). The trick maintains a convex hull (lower envelope) of lines y = b[j]·x + dp[j]. For a query at x=a[i], the minimum is found on this hull. If a[i] is monotonically increasing, a pointer (deque) gives O(n) amortized. Otherwise, binary search on the hull gives O(n log n). Used in task scheduling, slope trick DP, and knapsack variants.

Divide and Conquer (D&C) DP optimization applies when the optimal split point opt(i) is monotone: if opt(i) ≤ opt(i+1) for all i. For each dp[i][j] = min over k in [lo, hi] of cost(k, j) + dp[i-1][k], instead of checking all k for each j, use D&C: find opt for the middle j, then recurse left with k ≤ opt and right with k ≥ opt. This reduces O(n²) transitions per layer to O(n log n). Total for L layers: O(L·n log n). The monotone opt condition must be verified (often via the quadrangle inequality on the cost function). Used in optimal BST, matrix chain segmentation, and certain knapsack variants.

Euler tour (DFS in/out timestamps) assigns each node an entry time in[v] and exit time out[v] during DFS. The subtree of v corresponds exactly to the range [in[v], out[v]] in the Euler tour array. This reduces subtree sum/update queries to range queries on a flat array, solvable with Fenwick/segment trees in O(log n) per operation. The linearized array is constructed in DFS order. For LCA, a different Euler tour traverses each edge twice, producing a sequence where LCA(u,v) is the minimum-depth node between their first occurrences—enabling RMQ-based LCA in O(1) per query after O(n log n) preprocessing.

def euler_tour(root, adj, n):
    tin=[0]*n; tout=[0]*n; timer=[0]
    def dfs(v, parent):
        tin[v]=timer[0]; timer[0]+=1
        for u in adj[v]:
            if u!=parent: dfs(u,v)
        tout[v]=timer[0]; timer[0]+=1
    dfs(root,-1); return tin,tout

Small-to-Large merging (also called DSU on tree) processes subtree queries by merging smaller child sets into the larger. When combining two sets of sizes s and L (s ≤ L), each element of the smaller set is inserted into the larger, costing O(s log(L+s)). Each element can be 'the smaller side' at most O(log n) times (because after each merge its set at least doubles), giving O(n log n) total insertions. Space is O(n). This technique solves: count distinct values in subtrees, find most frequent value in subtrees, and dynamic connectivity problems. It is simpler to implement than HLD for many offline tree problems.

FFT computes the Discrete Fourier Transform in O(n log n) vs O(n²) for naive DFT. For polynomial multiplication: represent polynomial A of degree n-1 as n coefficients, evaluate at n points using FFT (O(n log n)), multiply point-wise with polynomial B evaluated at the same points (O(n)), then inverse FFT to recover product coefficients (O(n log n)). Total: O(n log n) vs O(n²) for coefficient-by-coefficient convolution. The Cooley-Tukey radix-2 FFT divides the n-point DFT into two n/2-point DFTs of even and odd indexed coefficients recursively. Applications: large integer multiplication, string convolution, and signal processing.

During DFS of a directed graph, edges are classified by the relationship between discovery/finish times: Tree edges connect a vertex to an undiscovered vertex (in the DFS tree). Back edges connect a vertex to an ancestor in the DFS tree (u→v where v is an ancestor; indicates a cycle). Forward edges connect a vertex to a descendant not via tree edge (u→v where v is already finished and discovered later than u). Cross edges connect vertices with no ancestor-descendant relationship. In undirected graphs, only tree edges and back edges exist. Back edges are the key indicator for cycle detection in directed graphs.

The Josephus problem: n people stand in a circle; every k-th person is eliminated; find the last survivor's position. For k=2 (classic), position of survivor J(n) = 2·J(n-1) mod (2·(n-1)) + 1, or using bit manipulation: if n = 2^m + L, answer = 2L + 1. For general k: J(1) = 0; J(n) = (J(n-1) + k) mod n. This O(n) recurrence computes the 0-indexed survivor position. The O(n log n) variant uses a Fenwick tree or order-statistics tree to simulate the process directly, supporting arbitrary k. Used in distributed systems for leader election and in competitive programming.

def josephus(n, k):
    pos = 0
    for i in range(2, n+1):
        pos = (pos + k) % i
    return pos  # 0-indexed survivor

By the max-flow min-cut theorem, the minimum cut between any source-sink pair equals the maximum flow between them. The Gomory-Hu tree compactly represents all n(n-1)/2 pairwise minimum cuts in an undirected graph using only n-1 max-flow computations (compared to the naive n(n-1)/2). The tree has the same vertex set; the minimum cut between any two vertices u, v equals the minimum edge weight on the unique path between u and v in the Gomory-Hu tree. Applications include network reliability analysis, connectivity problems, and finding the global minimum cut (Stoer-Wagner algorithm does this in O(V³) without explicit max-flow).

Amortized analysis assigns average cost to operations in a sequence, even if individual operations vary. Three techniques: (1) Aggregate method: total cost of n operations / n. Example: dynamic array doubling costs O(n) total insertions, so O(1) amortized. (2) Accounting method: assign 'credits' to cheap operations to pay for expensive ones; credit must always be non-negative. (3) Potential method: define a potential function Φ(state); amortized cost = actual cost + ΔΦ. If Φ stays non-negative and starts at 0, sum of amortized costs ≥ actual total cost. Used to analyze splay trees (O(log n) amortized), Union-Find with path compression, and stack operations.

Sqrt decomposition divides an array of n elements into blocks of size ≈ sqrt(n). Each block stores a precomputed aggregate (sum, min, max). Point update: update the element and the block aggregate in O(1). Range query [l, r]: fully covered blocks contribute their precomputed aggregate in O(1) each; partial blocks at the ends are iterated element by element. At most 2 partial blocks, each of size ≤ sqrt(n), and at most sqrt(n) full blocks: total O(sqrt n) per query. Space is O(n). Simpler to implement than segment trees, but slower. Used for Mo's algorithm (offline range queries in O((n+q)·sqrt(n))).

import math
def build_sqrt(arr):
    n=len(arr); B=int(math.sqrt(n))
    blocks=[0]*((n+B-1)//B)
    for i,v in enumerate(arr): blocks[i//B]+=v
    def query(l,r):
        s=0
        while l<=r:
            if l%B==0 and l+B-1<=r: s+=blocks[l//B]; l+=B
            else: s+=arr[l]; l+=1
        return s
    return query

Longest Common Extension LCE(i, j) is the length of the longest common prefix of suffixes starting at positions i and j. Using suffix arrays and LCP arrays, LCE(i, j) = RMQ(rank[i], rank[j]) on the LCP array, where rank[i] is the position of suffix i in the sorted suffix array. Range Minimum Query (RMQ) on the LCP array is preprocessed in O(n log n) using a sparse table, then answered in O(1). So LCE is O(1) per query after O(n log n) preprocessing. Applications: longest repeated substring, palindrome detection, string comparison in suffix-array-based algorithms, and DNA sequence alignment.

DSU on tree processes each node v by: first handling all light children (non-heavy) and discarding their data, then processing the heavy child and keeping its data structure. For each light child, iterate its subtree and insert into the data structure—each node is part of at most O(log n) light-child subtrees (heavy path decomposition guarantee), giving O(n log n) insertions total. This is distinct from small-to-large merging: DSU on tree uses a single shared data structure with selective clearing. It answers queries like 'count distinct colors in subtree' or 'most frequent element in subtree' offline in O(n log n).