Concepts18
Think Backwards (Reverse Thinking)
Think Backwards is a problem‑solving pattern where you reverse time or direction so hard deletions become easy insertions and the final state becomes the starting point.
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.
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.