Concepts158
Segment Tree with Range Affine Transformation
A segment tree with lazy propagation can support range updates of the form x → a·x + b (affine transformations) and range-sum queries in O(log n) per operation.
Bitset Optimization
Bitset optimization exploits word-level parallelism so one CPU instruction processes 64 bits at once on typical 64-bit machines.
Floor Sum Formula
The floor sum computes S(n,m,a,b) = sum_{i=0}^{n-1} floor((a i + b)/m) efficiently in O(log(min(a,m))) time.
Tree Isomorphism
Tree isomorphism asks whether two trees have exactly the same shape, ignoring vertex names.
Harmonic Lemma
The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).
DP on Broken Profile - Plug DP
Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
Matrix Exponentiation - Advanced
Matrix exponentiation turns repeated linear transitions into fast O(n^{3} log k) computation using exponentiation by squaring.
Top Tree
Top trees are dynamic tree data structures that represent a forest as a hierarchy of clusters, allowing O(log n) amortized time for link, cut, path queries/updates, and many subtree queries.
Game Theory - Nim
Nim is a two-player impartial game with several piles where a move removes any positive number of stones from exactly one pile.
Game Theory - Calculation Techniques
Sprague–Grundy theory converts any impartial, normal-play game into an equivalent Nim heap using a Grundy number.
Linearity of Expectation Applications
Linearity of expectation says the expected value of a sum equals the sum of expected values, even if the variables are dependent.
Expected Value
Expected value is the long-run average outcome of a random variable if you could repeat the experiment many times.