Modules
Analysis Root Finding Algorithm
for given f(x), find x such that f(x) = 0
Minimum Spanning Arborescence
similar to array_compression_with_argsort.rs
but each rank is unique.
if same value, sort by original index.
binary function
for sequence, see crate::binary_search_on_sequence.
for sequence, see crate::binary_search_on_sequence.
return undirected edges
input: bidirected adjacency list (undirected graph)
output: undirected edges [(u, v)] u < v. (but not sorted vertically)
(deal with no given priority between u and v, and among edges.)
make a bfs tree from given undirected csgraph edges.
return added flagged boolean result.
if the given graph is not connected,
make a bfs tree for the connected component containing source node.
find a pair of center nodes of the given unweited tree graph.
if tree diameter is even
or number of nodes in the path is odd,
two center nodes are same.
compute connected components on undirected graphs.
static range query for group like.
on undirected unicyclic simple graph.
detect each node is in the cycle or not.
manage minimum weigted edges.
dynamic tensor shape for static tensor.
euler tour teqnique
related
find a farthest node from any node in O(1)
a farthest node from each node is one of the tree diameter terminals.
Fast Fourier Transform
Cooley-Tukey’s Algorithm
Iterative Inplace
Fast Fourier Transform
Cooley-Tukey’s Algorithm
Recurse
mainly used in competitive programming
template main function.
fenwick tree (binary indexed tree)
interface is 0-indexed.
cumulative sum of cumulative sum.
cumulative sum of cumulative sum of cumulative sum.
inspired by numpy.flatnonzero
from any node
bfs from multiple nodes in the same bfs. O(N + M)
greatest common divisor on integer gcd(a, b)
a, b \in \Z.
0 := identity element and empty product here.
gcd(0, 0) := 0
\prod_{\emptyset} := 0
heavy light decomposition
an algorithm on undirected tree.
integer sqrt
integer square root digit by digit recursive
integer square root with linear naive algorithm
integer square root with binary search
integer square root with binary search
integer square root with addition
linear with subtraction
reference
https://en.wikipedia.org/wiki/Integer_square_root
integer square root with newton’s method
Inversion (Descrete Math)
find a node step by k edges from u for each query in offline
add a pattern of labels to nodes in the bipartite graph (true/false)
if the given graph is not bipartite, return None
least common multiple
level ancestor on tree with doubing (or binary lifting)
not only tree, but accept all the functional graph like structure
with parent and depth for each node.
for example, unicyclic tree (each node in the cycle is root) is ok.
Longest Common Subsequence
not confused with Longest Common Substring
lowest common ancestor
functionality
push arbitrary,
pop median
find median,
deal with 3 kinds of composition queries.
f(x) := f(x) + a
f(x) := max(f(x), a)
f(x) := min(f(x), a)
Minimum Spanning Tree
reexporting
well-known modular inverse algorithms.
inverse by Fermat’s Little Theorem.
for prime modulus.
extension of std::ops
Newton’s Method
f(x) must be differentiabl and f’(x) != 0
example
f(x) = x^2 - 10.
f’(x) = 2x
x = 3.16227…
TODO: use generic instead of f64 accepting int, big-rational, etc.
extension of std::ops.
reexporting pollard rho related algorithms.
to avoid floating point error
number theory algorithms on primality
this does not pass test.
Priority Queue
example
enumerate(10, 20)
= [11, 13, 17, 19]
example
enumerate(10, 20)
= [11, 13, 17, 19]
example
enumerate(10, 20)
= [11, 13, 17, 19]
example
factorize(2, 8)
= [2, 3, 2, 2, 5, 2, 3, 7]
example
factorize(2, 8)
= [(2, 4), (3, 2), (5, 1), (7, 1)]
example
factorize(2, 8)
= [(2, 4), (3, 2), (5, 1), (7, 1)]
example
factorize(2, 8)
= [[2], [3], [2, 2], [5], [2, 3], [7]]
example
factorize(2, 8)
= [[(2, 1)], [(3, 1)], [(2, 2)], [(5, 1)], [(2, 1), (3, 1)], [(7, 1)]]
sieve of sundaram
sparse table
reexporting shortest path faster algorithm.
reference
https://en.wikipedia.org/wiki/Modular_arithmetic#Properties
static tensor shape for static tensor.
module name is following Go’s package.
strongly connected components
special case of dual unbounded knapsack table just.
that all weights are 1.
Disjoint-Set-Union (DSU) or Union-Find (UF).
don’t confused with matrix rotation.
this is the matrix for rotation of vectors.
vector space algebra
Macros
reference
https://users.rust-lang.org/t/show-value-only-in-debug-mode/43686/3