Concepts9
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.
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.
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.
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.
Minimum Spanning Tree - Prim
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.