Concepts16
Stars and Bars
Stars and Bars counts the ways to distribute n identical items into k distinct bins using combinations.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
Sieve of Eratosthenes
The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.
GCD and Euclidean Algorithm
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.
DSU on Tree (Sack)
DSU on Tree (also called the Sack technique) answers many subtree queries in O(n \log n) by keeping data from the heavy child and temporarily re-adding light subtrees.
Z-Function
The Z-function of a string S computes for each position i the length of the longest substring starting at i that matches the prefix of S.
Exchange Arguments in DP
An exchange argument proves that any optimal solution can be reordered to satisfy a simple sorting rule by showing that swapping adjacent out-of-order elements never helps.
Digit DP
Digit DP is a dynamic programming technique for counting or aggregating values over all integers in a range that satisfy a digit-based property.
Gaussian Elimination over GF(2)
Gaussian elimination over GF(2) is ordinary Gaussian elimination where addition and subtraction are XOR and multiplication is AND.
Linear Recurrence
A linear recurrence defines each term as a fixed linear combination of a small, fixed number of previous terms.
Virtual Tree (Auxiliary Tree)
A Virtual Tree (Auxiliary Tree) compresses a large tree into a much smaller tree that contains only the k important nodes and the LCAs needed to keep them connected.
Lowest Common Ancestor (LCA)
The Lowest Common Ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both.