Advanced families and when they become useful

The main chapters cover the foundation. This chapter lists more advanced topics, and when each becomes worth learning. It's a map for further study; a table can't teach a technique on its own.

Topic	When to look at it	Key idea, or what you must prove
Divide and conquer	Pairs that cross between two halves can be handled quickly	Solve each half, and count every pair that crosses the split.
Merge sort counting	Count pairs (i, j) where the values satisfy an inequality	Sorted halves let one forward scan count the crossing pairs before merging.
Sweep line	Which items are active changes at sorted times or positions	Process events in order, decide how ties work, and keep the set of active items.
Meet in the middle	All subsets is too many, but half the subsets fits	Combine compatible halves without losing any rule.
Digit DP	Count numbers up to a huge bound with rules on their digits	Track the position, whether you're still matching the bound, and enough digit history.
State machine DP	Each step depends on a small mode, like holding a stock	Define the allowed moves, and whether updates use yesterday's or today's values.
Rerooting DP	You need a tree answer for every possible root	Combine what comes from the children and from the parent's side, without counting anything twice.
Binary lifting	Many "kth ancestor" or jump queries	Precompute jumps of 1, 2, 4, 8, … and combine them using the distance's binary digits.
Euler tour	Turn "is it in this subtree?" into a range query	Entry and exit times give each subtree one continuous range.
Minimum spanning tree	Connect every node with the least total edge weight	Use a cut or swap argument. Shortest routes are a different goal.
Strongly connected components	Treat each directed cycle as one unit	Merge nodes that can reach each other, which leaves a graph with no cycles.
Bridges and articulation points	Find edges or nodes whose removal disconnects the graph	Low-link values track what a DFS subtree can reach without its parent edge.
Eulerian path	Use every edge exactly once	Check degree and connectivity conditions. Edges and nodes are different questions.
All-pairs shortest paths	Many start-to-end queries on a small graph	Floyd–Warshall allows one more middle node per round; O(V³).
Max flow and matching	Assignments with capacities, or routes that can't share edges	Reverse edges let you undo earlier choices; prove the problem maps onto flow.
0-1 BFS	Every edge costs exactly 0 or 1	Push 0-cost moves to the front of a deque and 1-cost moves to the back.
KMP and the Z function	Strings with repeated prefix matches	Reuse what already matched instead of restarting at every position.
Manacher's algorithm	Palindrome lengths at every center in O(n)	Reuse mirrored information inside a known palindrome, then extend.
Sparse table	Range minimum (or similar) on a list that never changes	Precompute blocks of length 2ᵏ; overlapping blocks are fine for minimum and maximum.
DP speedups using order or convexity	A recurrence has extra structure	Prove the property you rely on; a familiar DP shape isn't enough.
Game DP	Two players take turns, each playing their best	Say what the current player's value means and how a move switches whose turn it is.
Geometry	The problem is about orientation, containment, or position in space	Define exact tests, the special cases, and how much numeric precision you need.

In digit DP, leading zeros may mean "no digit chosen yet" rather than real zeros. Track whether the digits so far exactly match the bound; once you're below it, later digits are free. The memoization key must include everything that affects which digits can come next.

In game DP, storing a score difference often makes alternating turns simple. Your advantage is what you gain from a move minus your opponent's best advantage afterward. That only works for games where one player's gain is the other's loss. Don't use it for cooperative games.

A minimum spanning tree doesn't give shortest paths. The graph might have a short direct route that the tree leaves out. Ask whether you're adding up each chosen edge once, or adding up the cost of travelling a route.

In divide and conquer, count the work to combine the halves. Merge sort counting is usually O(n log n), but combining in O(n²) wipes out the gain. When counting pairs like a[i] > 2 × a[j], convert to a wider type before multiplying, and keep the original order of indexes through the split.

Advanced practice, when you need it: LC 493 Reverse Pairs, LC 1851 Minimum Interval to Include Each Query, LC 1755 Closest Subsequence Sum, LC 2035 Partition Array Into Two Arrays to Minimize Sum Difference, LC 2376 Count Special Integers, LC 309 Best Time to Buy and Sell Stock with Cooldown, LC 834 Sum of Distances in Tree, LC 1483 Kth Ancestor of a Tree Node, LC 1584 Min Cost to Connect All Points, LC 1192 Critical Connections in a Network, LC 332 Reconstruct Itinerary, LC 486 Predict the Winner, LC 1392 Longest Happy Prefix.

Before you code an unfamiliar advanced technique, read a full explanation of it. CP-Algorithms S16 covers most of them. Learn the fact that makes the technique correct, and keep a simple correct version around to compare against on small inputs.