All Templates | Informatics Template Lib

Sieve Prime Factors — SPF + Fast Factorization

#Sieve#Prime-Factors

$ cat sieve-pr..

template_upper-bound.cpp

Upper Bound

#binary-search#upper-bound#predicate

Find the last element < target in a sorted array using binary search.

$ cat upper-bo..

template_trie.cpp

Trie

#trie#prefix-tree#string+1

Prefix tree for string storage with insert, search, prefix check, and erase in O(|s|).

$ cat trie

template_ternary-search.cpp

Ternary Search

#ternary-search#unimodal#optimization+1

Find the max or min of a unimodal function on a continuous interval in O(log(range/eps)).

$ cat ternary-..

template_tarjan.cpp

Tarjan's Algorithm

template_sqrt-decomposition.cpp

SCC decomposition, bridges, and articulation points in a single O(V+E) DFS pass.

#tarjan#scc#bridges+2

$ cat tarjan

SQRT Decomposition

#sqrt-decomposition#bucket#range-query+1

Square root decomposition with sorted blocks for range counting queries and point updates in O(sqrt n).

$ cat sqrt-dec..

template_splay-tree.cpp

Splay Tree

#splay-tree#bst#self-adjusting+1

Self-adjusting BST with O(log n) amortized operations via splay rotations.

$ cat splay-tr..

template_sparse-table.cpp

Sparse Table

#sparse-table#rmq#range-minimum+1

Static range query structure — O(1) for idempotent operations (min/max/gcd), O(log n) for non-idempotent.

$ cat sparse-t..

template_sieve.cpp

Sieve of Eratosthenes

#sieve#prime#number-theory+2

Linear sieve computing primes, smallest prime factor (SPF), Euler's totient, and Mobius function in O(n).

$ cat sieve

template_segment-tree-2d.cpp

2D Segment Tree

#segment-tree#2d#matrix+1

Nested segment tree for 2D point update and rectangle queries in O(log n * log m).

$ cat segment-..

template_segment-tree.cpp

Segment Tree

#segment-tree#range-query#point-update

Classic segment tree with point update and range query for any associative operation.

$ cat segment-..

template_rolling-hash.cpp

Rolling Hash (Hashing)

#hashing#rolling-hash#double-hash+2

Polynomial rolling hash with double hashing for collision-resistant O(1) substring comparison.

$ cat rolling-..

template_prim-mst.cpp

Prim's MST

#prim#mst#minimum-spanning-tree+1

Minimum spanning tree using priority queue — greedy cut-based approach in O(E log V).

$ cat prim-mst

template_primitive-root.cpp

Primitive Root

#primitive-root#generator#modular+2

Find the smallest primitive root (generator) modulo a prime p.

$ cat primitiv..

template_prefix-sum-2d.cpp

Prefix Sum 2D

#prefix-sum#2d#range-query+2

2D prefix sum for O(1) rectangle sum queries on a static grid.

$ cat prefix-s..

template_pollard-rho.cpp

Pollard's Rho Factorization

#factorization#pollard-rho#number-theory+1

Factorize 64-bit integers into primes using Pollard's Rho with Miller-Rabin primality testing.

$ cat pollard-..

template_persistent-segment-tree.cpp

Persistent Segment Tree

#persistent#segment-tree#versioned+1

Segment tree preserving all versions via path copying — O(log n) per update, O(n + q log n) total memory.

$ cat persiste..

template_partial-sum-2d.cpp

Partial Sum 2D (Difference Array)

#difference-array#2d#range-update+1

2D difference array for O(1) range updates and O(n*m) final propagation.

$ cat partial-..

template_ordered-set.cpp

Ordered Set

#ordered-set#pbds#order-statistics+1

Policy-based order-statistics tree — find k-th element and count elements less than x in O(log n).

$ cat ordered-..

template_number-theory-basics.cpp

Number Theory Basics

#prime#factorization#totient+2

Primality test, factorization, Euler's totient, divisors, integer sqrt, and perfect power check.

$ cat number-t..

template_mos-on-trees.cpp

Mo's Algorithm on Trees

#mo-algorithm#tree#euler-tour+2

Mo's algorithm adapted for tree path queries using Euler tour flattening and LCA via binary lifting.

$ cat mos-on-t..

template_mos-algorithm.cpp

Mo's Algorithm

#mo-algorithm#offline#range-query+2

Offline range query processing with Hilbert curve ordering for optimal cache performance.

$ cat mos-algo..

template_monotonic-stack.cpp

Monotonic Stack

#monotonic-stack#next-greater#next-smaller+1

Next/previous greater/smaller element queries in O(n) using a monotonic stack.

$ cat monotoni..

template_monotonic-queue.cpp

Monotonic Queue

#monotonic-queue#sliding-window#deque+1

Sliding window min/max in O(1) amortized using the two-stack queue pattern.

$ cat monotoni..

template_modular-inverse.cpp

Modular Inverse

#modular-inverse#fermat#extended-gcd+1

Modular multiplicative inverse via Fermat's little theorem, extended Euclidean, and linear precomputation.

$ cat modular-..

template_modular-arithmetic-helpers.cpp

Modular Arithmetic Helpers

Safe modular add, multiply, binary exponentiation, Russian peasant multiplication, and big mod.

#modular#binpow#int128+1

$ cat modular-..

template_modint.cpp

Modular Integer (ModInt)

#modint#modular#arithmetic+1

Type-safe modular arithmetic with operator overloading for clean competitive programming code.

$ cat modint

template_miller-rabin.cpp

Miller-Rabin Primality Test

#primality-test#miller-rabin#deterministic+1

Deterministic Miller-Rabin primality test for 64-bit integers using verified witness sets.

$ cat miller-r..

template_matrix-exponentiation.cpp

Matrix Exponentiation

#matrix#exponentiation#linear-recurrence+1

Binary exponentiation on square matrices for solving linear recurrences in O(n^3 log k).

$ cat matrix-e..

template_math-utilities.cpp

Math Utilities

#base-conversion#summation#multiples+1

Base conversion, range summation, counting/summing multiples, and log base.

$ cat math-uti..

template_manacher.cpp

Manacher's Algorithm

#manacher#palindrome#string+1

Find all palindromic substrings in O(n) time using linear expansion with symmetry reuse.

$ cat manacher

template_lower-bound.cpp

Lower Bound

#binary-search#lower-bound#predicate

Find the first element >= target in a sorted array using binary search.

$ cat lower-bo..

template_link-cut-tree.cpp

Link-Cut Tree

#link-cut-tree#splay#dynamic-tree+1

Dynamic forest structure supporting link, cut, and path queries in O(log n) amortized.

$ cat link-cut..

template_lca-weighted.cpp

LCA Weighted

#lca#binary-lifting#weighted-tree+2

LCA with path aggregate queries (sum/max/min) on weighted trees using binary lifting in O(log n).

$ cat lca-weig..

template_lca.cpp

LCA — Lowest Common Ancestor

#lca#binary-lifting#tree+1

Binary lifting for LCA, distance, and k-th ancestor queries on unweighted trees in O(log n).

$ cat lca

template_lazy-segment-tree.cpp

Lazy Segment Tree

#segment-tree#lazy-propagation#range-update+1

Segment tree with lazy propagation — supports range updates and range queries in O(log n).

$ cat lazy-seg..

template_kuhn-matching.cpp

Kuhn's Matching

#bipartite#matching#kuhn+1

Maximum bipartite matching via augmenting paths in O(V*E).

$ cat kuhn-mat..

template_kmp.cpp

KMP Algorithm

#kmp#pattern-matching#prefix-function+1

Knuth-Morris-Pratt pattern matching and prefix function in O(n + m).

$ cat kmp

template_kadane.cpp

Kadane's Algorithm

[Dynamic Programming]

Maximum contiguous subarray sum in O(n) time using linear DP.

#kadane#maximum-subarray#dp+1

$ cat kadane

template_int128-io.cpp

128-bit Integer I/O

#int128#io#gcc-extension+1

Read and print __int128 values — a GCC extension for 128-bit signed integers not supported by standard cin/cout.

$ cat int128-i..

template_inclusion-exclusion.cpp

Inclusion-Exclusion

#inclusion-exclusion#coprime#bitmask+1

Count elements satisfying none/any of n properties using bitmask inclusion-exclusion.

$ cat inclusio..

template_implicit-splay-tree.cpp

Implicit Splay Tree

#splay-tree#implicit#sequence+2

Index-keyed splay tree for sequence operations — insert, erase, range query with lazy propagation.

$ cat implicit..

template_hld.cpp

Heavy-Light Decomposition

#hld#heavy-light#decomposition+2

Decomposes a tree into chains for O(log^2 n) path queries using a segment tree.

$ cat hld

template_heap.cpp

Binary Heap

#heap#priority-queue#binary-heap

Min/max binary heap with push, pop, and top in O(log n).

$ cat heap

template_hash-segment-tree.cpp

Hash Segment Tree

#segment-tree#hashing#dynamic-string+1

Segment tree storing double hash values for range substring hashing with point updates in O(log n).

$ cat hash-seg..

template_hashed-deque.cpp

Hashed Deque

#hashing#deque#rolling-hash+1

Deque with O(1) rolling polynomial double hash for constant-time equality comparison.

$ cat hashed-d..

template_graph-traversal.cpp

Graph Traversal

template_graph-representation.cpp

DFS and BFS with bipartite check, cycle detection, topological sort, and path reconstruction.

#dfs#bfs#bipartite+2

$ cat graph-tr..

Graph Representation

#graph#adjacency-list#head-array+1

Linked-list (head array) adjacency — cache-friendly graph representation for contests.

$ cat graph-re..

template_geometry-points.cpp

Geometry Points

template_gcd-lcm-extended-gcd.cpp

Generic 2D point with full operator support: dot, cross, distance, rotation, unit, normal.

#geometry#point#vector+2

$ cat geometry..

GCD, LCM & Extended GCD

template_floyd-warshall.cpp

GCD, LCM, Extended Euclidean algorithm, and linear Diophantine equation solver.

#gcd#lcm#extended-gcd+2

$ cat gcd-lcm-..

Floyd-Warshall

#floyd-warshall#all-pairs#shortest-path+2

All-pairs shortest paths via O(V^3) dynamic programming on the adjacency matrix.

$ cat floyd-wa..

template_fenwick-tree-range.cpp

Fenwick Tree Range

template_fenwick-tree-2d.cpp

Fenwick tree supporting both range add and range sum queries using two BITs.

#fenwick#bit#range-add+1

$ cat fenwick-..

2D Fenwick Tree

template_fenwick-tree.cpp

2D Binary Indexed Tree for point updates and rectangle sum queries in O(log n * log m).

#fenwick#bit#2d+2

$ cat fenwick-..

Fenwick Tree

#fenwick#bit#binary-indexed-tree+2

Binary Indexed Tree for prefix sum queries and point updates in O(log n).

$ cat fenwick-..

template_dsu.cpp

DSU

#dsu#union-find#disjoint-set+1

Disjoint Set Union with path compression and union by size in near-constant amortized time.

$ cat dsu

template_dijkstra.cpp

Dijkstra's Algorithm

#dijkstra#shortest-path#priority-queue+1

Shortest path in non-negative weighted graphs using priority queue relaxation in O((V+E) log V).

$ cat dijkstra

template_digit-dp.cpp

Digit DP

[Dynamic Programming]

Count numbers in [L, R] satisfying digit-level constraints using memoized recursion.

#digit-dp#dp#counting+1

$ cat digit-dp

template_cp-starter.cpp

CP Starter

[Utilities]by Mohamed Ibrahim

Modern competitive programming starter template with fast I/O, common aliases, and contest-ready boilerplate.

#template#boilerplate#fast-io+1

$ cat cp-start..

template_coordinate-compression.cpp

Coordinate Compression

#coordinate-compression#discretization#rank

Maps sparse values to dense 0-indexed ranks for use with BIT/segment tree.

$ cat coordina..

template_convex-hull-trick.cpp

Convex Hull Trick (Li Chao Tree)

[Dynamic Programming]

Dynamic line container with O(log C) insert and min query using Li Chao segment tree.

#convex-hull-trick#cht#li-chao+2

$ cat convex-h..

template_convex-hull-andrew.cpp

Convex Hull (Andrew's)

#convex-hull#geometry#monotone-chain+1

Andrew's monotone chain algorithm for convex hull in O(n log n).

$ cat convex-h..

template_combinatorics-counting.cpp

Combinatorics Counting

template_centroid-decomposition.cpp

Non-modular nCr, nPr, and Legendre's formula for prime power in factorials.

#nCr#nPr#factorial+2

$ cat combinat..

Centroid Decomposition

#centroid#decomposition#tree+1

Divide-and-conquer on trees via centroid selection for O(n log n) path processing.

$ cat centroid..

template_catalan-numbers.cpp

Catalan Numbers

#catalan#combinatorics#counting

Catalan number computation via closed-form formula and DP recurrence.

$ cat catalan-..

template_burnsides-lemma.cpp

Burnside's Lemma

#burnside#counting#symmetry+2

Count distinct objects under symmetry (rotations) using Burnside's lemma.

$ cat burnside..

template_bit-utilities.cpp

Bit Utilities

[Bit Manipulation]

Common bit manipulation operations — check, set, clear, toggle, popcount, subset enumeration.

#bit-manipulation#bitmask#subset+1

$ cat bit-util..

template_binomial-coefficients.cpp

Binomial Coefficients

Precomputed factorial and inverse factorial for O(1) nCr and nPr queries modulo a prime.

#binomial#nCr#nPr+2

$ cat binomial..

template_binary-trie.cpp

Binary Trie

template_binary-search-tree.cpp

Trie on bit representation of integers — supports insert, erase, and XOR maximum query.

#binary-trie#xor#bit+2

$ cat binary-t..

Binary Search Tree

#bst#binary-search-tree#traversal

Basic BST with insert, delete, search, min/max, and all four traversal orders.

$ cat binary-s..

template_binary-search-on-number.cpp

Binary Search

#binary-search#sorted-array#search

Classic binary search for finding a target value in a sorted array in O(log n).

$ cat binary-s..

template_binary-search-on-answer.cpp

Binary Search on Answer

#binary-search#predicate#optimization+1

Search for the optimal value satisfying a monotonic predicate in O(log n).

$ cat binary-s..

template_binary-exponentiation.cpp

Binary Exponentiation

[Algebra]by midoriya-dev

Fast exponentiation using binary representation of the exponent in O(log n) multiplications.

#binary-exponentiation#power#modular+1

$ cat binary-e..

template_big-integer.cpp

Big Integer

#bigint#arbitrary-precision#big-integer+1

Non-negative arbitrary-precision integer with addition, subtraction, multiplication, division, and modulo.

$ cat big-inte..

template_bellman-ford.cpp

Bellman-Ford

#bellman-ford#shortest-path#negative-weights+1

Shortest path with negative edge weights and negative cycle detection in O(V*E).

$ cat bellman-..

template_basic-geometry-checks.cpp

Basic Geometry Checks

#geometry#triangle#distance+2

Triangle validity, Euclidean distance, and collinearity check using cross product.

$ cat basic-ge..

template_2d-geometry.cpp

2D Geometry