This is a fork of saketh-are/algo-lib, with a few changes according to my personal preferences.
Contents
- Usage
- Data Structures
- Union Find
- Union Find (Bipartite)
- Union Find (Rewindable)
- Segment Tree
- Segment Tree (Lazy Propagation)
- Segment Tree (Persistent)
- Segment Tree (Searchable)
- Binary Indexed Tree
- Sparse Table
- Sqrt Decomposition (Range Update, Point Query)
- Line Container
- Line Container (Monotonic)
- Static to Dynamic Transformation
- Graphs
- Misc
- Numeric
- Strings
Usage
All classes compile on C++ 17.
Some files require the contents of other files, denoted by a comment // {{{ <filepath> }}}
. If you would like to generate buildable code from the usage examples, a small script is provided to pull in dependencies. Run:
python2 expand_dependencies.py <input path> <output path> <path to repository root>
Passing function objects as arguments
Some functions expect function objects as arguments, typically either:
- A binary operation used to accumulate stored values (e.g. segment_tree's constructor)
- A unary operation used to initialize a range of elements (e.g. segment_tree's assign)
You can pass a function pointer:
int add(int a, int b) {
return a + b;
}
segment_tree<int, int(*)(int, int)> s(SZ, 0, add);
Or a lambda expression:
auto add = [](int a, int b) {
return a + b;
};
segment_tree<int, decltype(add)> s(SZ, 0, add);
Or a struct with operator ():
struct adder {
int operator()(int a, int b) {
return a + b;
}
};
segment_tree<int, adder> s(SZ, 0, adder{});
functional.h defines some useful function objects:
segment_tree<int, plus<int>> s(SZ, 0, plus<int>());
Since C++17 you can generally omit the template arguments:
segment_tree s(SZ, 0, [](int a, int b) { return a + b; });
Passing iterators as arguments
Some functions expect a pair of iterators first
and last
as arguments (e.g. knuth_morris_pratt's constructor).
- The range of elements operated on is always the semi-open interval
[first, last)
.
You'll typically pass either string iterators:
string s;
knuth_morris_pratt kmp(s.begin(), s.end());
Or vector iterators:
vector<int> s;
knuth_morris_pratt kmp(s.begin(), s.end());
Data Structures
Union Find
Maintains a partition of the set {0, 1, ..., N-1}
supporting:
- Retrieval of an identifier for the subset containing a specified element
- Replacement of two specified subsets with their union
Amortized runtime complexity is near constant for both operations.
Usage Examples:
Union Find (Bipartite)
Maintains information about bipartitions of the set {0, 1, ..., N-1}
supporting:
- Constrainment of two specified elements to appearing in opposite subsets
- Constrainment of two specified elements to appearing in the same subset
- Constrainment of a specified element to a specified subset
- Counting the number of bipartitions satisfying all configured constraints
- Computing the smallest size of a particular subset over all satisfying bipartitions
Amortized runtime complexity is near constant for all operations.
Usage Examples:
Union Find (Rewindable)
Maintains a partition of the set {0, 1, ..., N-1}
supporting:
- Retrieval of an identifier for the subset containing a specified element in
O(log(N))
- Replacement of two specified subsets with their union in
O(1)
- Reversion of the most recent "union" operation in
O(1)
Can process a sequence of E
edge insertions and deletions in O(E log(E) log(N))
.
Usage Examples:
Segment Tree
Maintains an array of N
elements supporting:
- Modification of a specific element in
O(log(N))
- Accumulation of a range of elements in
O(log(N))
Usage Examples:
Segment Tree (Lazy Propagation)
Maintains an array of N
elements supporting:
- Modification of a range of elements in
O(log(N))
- Accumulation of a range of elements in
O(log(N))
Usage Examples:
Segment Tree (Persistent)
Maintains an array of N
elements supporting:
- Modification of a specific element at a specified point in time in
O(log(N))
- Accumulation of a range of elements as they were at a specified point in time in
O(log(N))
Writes must be made with non-decreasing timestamps; there is no restriction on reads. Reads and writes can be interspersed in an arbitrary fashion.
Consumes O(log(N))
additional memory on each write.
Usage Examples:
Segment Tree (Searchable)
Adds a binary search feature to the Segment Tree class which accepts an index first
and a predicate p
, returning the first index last
such that p(accumulate(first, last))
evaluates to true. Requires that the predicate is non-decreasing as last
increases.
Rounds up internal size to the next power of 2. For a segment tree over N
elements, search is O(log(N))
.
Usage Examples:
Binary Indexed Tree
Maintains an array of N
elements supporting:
- Modification of a specific element in
O(log(N))
- Accumulation of a prefix of elements in
O(log(N))
Less general than a Segment Tree; offers better constant factor performance.
Usage Examples:
Sparse Table
Accepts a static array of N
elements and an idempotent binary operation f
. Supports:
- Accumulation of a range of elements in
O(1)
Precomputation is O(N log(N))
. Typically used with f = min<T>
or f = max<T>
.
Usage Examples:
Sqrt Decomposition (Range Update, Point Query)
Maintains an array of N
elements supporting:
- Modification of a range of elements in
O(sqrt(N))
- Querying the value of a single element in
O(1)
Usage Examples:
Line Container
Maintains a collection of lines. Supports:
- Insertion of a line
f(x) = a * x + b
- Querying for the maximum value among all inserted lines at a specified value of
x
Runtime complexity for both operations is O(log(container size))
.
Usage Examples:
Line Container (Monotonic)
Maintains a collection of lines. Supports:
- Insertion of a line
f(x) = a * x + b
, wherea
is non-decreasing across all insertions - Querying for the maximum value among all inserted lines at a specified value of
x
Runtime complexity for insertion is amortized O(1)
. Runtime complexity for arbitrary queries is O(log(container size))
. If get_maximum_monotonic
is used, total runtime complexity over a sequence of queries made with non-decreasing x
is linear.
Usage Examples:
Static to Dynamic Transformation
Adds the ability to insert new elements into a static data structure. Requires that queries to the data structure are decomposable; for any pair of disjoint sets of elements, the answer to a query over their union must be computable from answers to the query over the individual sets.
Over a sequence of N
insertions, the K-th most recently inserted element is involved in log(K)
constructions of the static data structure. A query made after N
elements have been inserted is decomposed into log(N)
queries on disjoint subsets of the inserted elements.
Usage Examples:
Graphs
Tree
Computes and stores basic properties of a rooted tree on V
nodes:
- The parent, depth, and subtree size of each node
- The neighbor list for each node in non-increasing order of subtree size
- A preorder traversal of the tree
Precomputation is O(V log(V))
to compute sorted neighbor lists and O(V)
otherwise.
Usage Examples:
Lowest Common Ancestor
Computes and stores the euler tour representation of a tree on V
nodes:
- Supports queries for the lowest common ancestor of two nodes in
O(1)
- Supports queries for the distance between two nodes in
O(1)
- Supports queries for whether the simple path between two nodes visits a third node in
O(1)
- Supports queries for whether a specified node is an ancestor of another in
O(1)
- Supports queries for the first step on the simple path between two nodes in
O(1)
Precomputation is O(V log(V))
.
Usage Examples:
Heavy Path Decomposition
Given a rooted tree on V
nodes, computes a permutation p
of its vertices such that:
- Any simple path in the tree can be decomposed into
log(V)
contiguous oriented intervals inp
- Any subtree's vertex set occurs as a single contiguous interval in
p
Accepts an instance of the Tree class. Additional precomputation is O(V)
.
Usage Examples:
Dijkstra
An implementation of Dijkstra's Algorithm for computing shortest path trees.
Runs in O(V + E log(E))
on a graph with V
vertices and E
edges.
Usage Examples:
Two Sat
Implication graph for boolean two-satisfiability. Constructs a satisfying assignment or detects that none exist. Runtime is linear in the size of the implication graph.
Classifies each variable as true in all satisfying assignments, false in all satisfying assignments, or neither. Runtime is O(N * N / MACHINE_WORD_SIZE)
.
Usage Examples:
Misc
Subset Sum
Given a set of integers with sum T
, computes its set of subset sums in O(T sqrt(T) / MACHINE_WORD_SIZE)
.
Usage Examples:
Count Distinct In Range
Processes a sequence of comparable elements and a parameter copies_allowed
. Supports queries for the number of elements in a specified range of the sequence if only the first copies_allowed
appearances of each distinct value are counted.
Usage Examples:
Numeric
ModNum
Performs modular arithmetic:
- Implements basic operators (
+
,-
,*
,/
) - Computes inverses in
O(log(MOD))
- Computes discrete logarithms in
O(sqrt(MOD))
- Caches roots of unity
- Caches factorials and inverse factorials to compute:
- Binomial coefficients in
O(1)
- Inverses in
O(1)
- Binomial coefficients in
MOD
is configured as a template parameter. If the modulus isn't known at compile-time, move MOD
inside the struct as a static member.
Usage Examples:
Number Theoretic Transform
Convolves polynomials over the field of integers modulo P
.
Requires that P
is prime. Let D
be the smallest power of 2 exceeding the degree of the returned polynomial. D
must divide P-1
.
The runtime complexity is O(D log(D))
.
Usage Examples:
Complex FFT
Convolves polynomials over the field of doubles.
Provides a routine for convolution of polynomials over the integers modulo P
without Number Theoretic Transform's constraint that D
divides P - 1
. This routine seems to be safe for N,M <= 150,000
but isn't precise enough for some adversarial cases around N = M = 180,000
.
Usage Examples:
Discrete Logarithm
Given integers x
, y
, and MOD
, computes and returns the smallest non-negative integer K
such that x^K === y (mod MOD)
. Returns -1
if no such integer exists. Runs in O(sqrt(MOD))
.
Usage Examples:
Tonelli-Shanks
Given integers n
and MOD
, computes and returns an integer r
such that r * r === n (mod MOD)
. Returns -1
if no such integer exists.
Requires that MOD
is a prime power. If MOD = 2^S * Q
with Q
odd, runs in O(S log(S) / log(log(S)))
.
Usage Examples:
BigNum (Add Power of 2, Compare)
Large integer representation. Starts with a representation of 0
and supports:
- Representation of the sum of a represented integer with an arbitrary power of 2
- Comparison of two represented integers
Runtime complexity for both operations is logarithmic in the number of digits of precision. Constructing a sum also consumes additional memory logarithmic in the number of digits of precision.
Usage Examples:
Strings
Knuth-Morris-Pratt
Given a string S
, computes for each prefix the longest proper suffix which is also a prefix of S
. Supports:
- Characterizing occurrences (and partial occurrences) of
S
in a specified patternT
inO(|T|)
Precomputation is O(|S|)
.
Usage Examples:
Z Algorithm
Given a string S
, computes the length of the longest common prefix between S
and each of its suffixes.
Runs in O(|S|)
.
Usage Examples:
Palindromes
Given a string S
:
- Computes the length of the longest palindrome centered at each character
- Computes the length of the longest palindrome centered between each pair of adjacent characters
- Supports queries for the length of the longest palindrome within a specified substring of
S
inO(log(|S|))
Precomputation is O(|S|)
. Additional precomputation for substring queries is O(|S| log(|S|))
.
Usage Examples:
Polynomial Hash
A rolling hash for probabilistic string equality checks. Supports:
- Hashing a character in
O(1)
- Concatenating two hashes in
O(1)
- Computing hashes for all prefixes of a given string
S
inO(|S|)
- Given prefix hashes for a string
S
, extracting the hash for an arbitrary substring ofS
inO(1)
Increasing parameter EvaluationPoints lowers the probability of two distinct strings producing the same hash.
Usage Examples:
Suffix Array
Given a string S
:
- Computes the lexicographic ordering of its suffixes
- Computes the length of longest common prefix between each pair of adjacent suffixes in the lexicographic ordering
- Supports queries for the longest common prefix between an arbitrary pair of suffixes
- Supports queries for the range of ranks at which a specified substring occurs
- Supports queries for the first occurrence of a specified substring
Precomputation is O(|S| log(|S|))
.
Usage Examples:
Suffix Automaton
Given a string S
, computes the minimal finite automaton accepting all suffixes of S
.
- Supports queries for the first occurrence in
S
of a specified patternT
inO(|T|)
- Supports queries for the number of occurrences in
S
of a specified patternT
inO(|T|)
Precomputation is O(|S|)
.
Usage Examples:
Trie
Given a collection of strings S
, supports:
- Computing the total number of occurrences over all strings in
S
within a specified patternT
inO(|T|)
- Computing the number of occurrences of each string in
S
within a specified patternT
inO(|S| + |T|)
- Finding the indices of all occurrences of each string in
S
within a specified patternT
inO(|T| + |S| + total number of occurrences)
Precomputation is linear in the sum of the lengths of the strings in S
.
Usage Examples:
Mutable String
Maintains a string over a finite alphabet, supporting:
- Modification of a specified character in
O(sqrt(|S|))
- Queries for the number of appearances of a specified pattern
T
in a specified substring ofS
inO(|T|sqrt(|S|))
Usage Examples:
Mutable String (Bitset)
Maintains a string over a finite alphabet, supporting:
- Modification of a specified character in
O(1)
- Queries for the number of appearances of a specified pattern
T
in a specified substring ofS
inO(|T| * |S| / MACHINE_WORD_SIZE)
Usage Examples: