i. Divide and Conquer

Split into independent halves, recurse, and handle what crosses the split. The combine step is where the work and the cleverness live. Its cost sets the total: $O(n)$ combine gives $O(n\log n)$, $O(n\log n)$ combine gives $O(n{\log }^{2}n)$.

Template

ll solve(int l, int r) {                     // [l, r)
    if (r - l == 1) return base(l);
    int m = (l + r) / 2;
    ll res = solve(l, m) + solve(m, r);
    res += crossing(l, m, r);                // objects with one part in each half
    return res;
}

Recursion depth is $O(\log n)$, so it’s safe. Allocate merge buffers once, globally.

Counting pairs across the middle

Every pair $(i,j)$ is “crossing” at exactly one level of the recursion, the one where $i$ and $j$ separate. With both halves sorted (merge sort order), crossing pairs are usually counted with two pointers.

Proof: every pair is crossing at exactly one level

Fix $i<j$. At the root, either they land in the same half (and recursion continues on that half) or in different halves (crossing, counted here, and the recursion never revisits this pair again since the two indices are never reunited in a single call). If they land in the same half, apply the same argument one level down. Since each level strictly shrinks the interval containing both $i,j$ until it can no longer hold both halves, this process terminates in at most ${\log }_{2}n$ steps at the unique level where $i,j$ first separate. So the pair is crossing at exactly one level, not zero (eventually some level must separate $i$ and $j$, since a single-element interval cannot) and not more than one (once separated, recursion never reconsiders the pair). $■$

Problem	Crossing step
inversions; pairs with $a_i>c{a}_j$	two pointers during the merge
pairs $i<j$ with $a_j-a_i\in [L,R]$	sorted halves, two pointers
subarrays with sum in $[L,R]$	sorted prefix sums of each half
closest pair of points	strip of width $2\delta$ sorted by $y$, at most 7 neighbours each
3D dominance, offline 2D updates	CDQ

Subarrays crossing the middle

For “count / optimise over all subarrays $[i,j]$ of $f$”, the subarrays with $i<m\le j$ split into a suffix of the left half and a prefix of the right half. Compute an aggregate for each left start (scanning left from $m$) and each right end (scanning right from $m$), then combine them with sorting, two pointers or a data structure. Example: count subarrays where $\max -\min =$ length $-1$ (permutation subarrays): split by whether the max and the min fall on the left or the right; each case is linear with two pointers. $O(n\log n)$ total.

Divide at the maximum (unbalanced D&C): for “subarrays whose maximum is $a_m$”, the split point is the maximum, not the middle. Iterate over the shorter side and query the longer side with a precomputed structure. Since each element is on the shorter side $O(\log n)$ times (like small-to-large), the total is $O(n\log n)$ times the query cost. This is a traversal of the Cartesian tree.

Proof: each element is on the shorter side $O(\log n)$ times

Charge an element $x$ once every time the subarray containing it is split and $x$ ends up on the side chosen for iteration (the shorter one). The subarray containing $x$ has some length $\ell$ before the split; since $x$ is on the shorter side, the new subarray containing $x$ has length $\le \ell /2$. So each charge at least halves the length of the interval containing $x$, starting from $n$ and bottoming out at $1$, giving at most ${\log }_{2}n$ charges. Summing over all $n$ elements, the total number of (element, split) charges — which is exactly the total work of “iterate over the shorter side” across the whole recursion — is $O(n\log n)$. $■$

Offline range queries by D&C

Answer queries $[l,r]$ for an operation that’s hard to combine (knapsack over a range, a “best subsequence” DP, path counts in a grid strip): recurse on $[lo,hi)$ with mid $m$. Queries with $l<m\le r$ are answered at this node; the others go to the side that contains them. At the node, compute for every $i\in [lo,m)$ the DP of $a[i..m)$ (a suffix DP growing leftwards), and for every $j\in [m,hi)$ the DP of $a[m..j]$, then combine the two DP states for each query.

• Range 0/1 knapsack queries “best value of $a[l..r]$ with capacity $C$”: $O(nC\log n+qC)$.
• Grid reachability queries “can $(r_1,c_1)$ reach $(r_2,c_2)$ moving right/down”: split rows at the middle, bitset of reachable middle-row cells from each source and to each target, $O(n{m}^2\log n/64)$.
• It’s the disjoint-sparse-table idea applied to arbitrary DP states (Disjoint Sparse Table).

Divide and conquer on other axes

• On time (segment tree over the query timeline): each element’s lifetime is $O(\log q)$ tree nodes; DFS the tree with a rollback structure. That’s offline dynamic connectivity, bipartiteness and XOR basis under deletions (Dynamic Connectivity).

Proof: a lifetime decomposes into $O(\log q)$ segment-tree nodes

This is the same fact that makes range updates on a segment tree cost $O(\log q)$ nodes: build a segment tree over the $q$ time slots (leaves = individual moments). A lifetime $[t_1,t_2)$ is covered by the canonical decomposition into disjoint segment-tree nodes used by any range-update-point-query segment tree. At each of the $O(\log q)$ depths, the decomposition contains at most 2 nodes (one partially covering the left boundary, one the right; internal depths in between contribute at most 2 fully-covered maximal nodes by the standard segment-tree range-decomposition argument). So the lifetime is stored in $O(\log q)$ nodes total, and inserting it into all of them costs $O(\log q)$ per element. $■$

• On values (“overall binary search”): recurse on the answer range $[lo,hi)$ with the queries whose answer lies there, applying the updates with values in $[lo,mid)$ to a BIT to split the queries. It’s parallel binary search written recursively, and it handles range $k$-th smallest with updates in $O((n+q){\log }^{2}n)$.
• On a tree: centroid decomposition gives depth $O(\log n)$, and every path passes through exactly one centroid in its component (Centroid Decomposition).
• On DP layers: monotone optimum splits, $O(n\log n)$ per layer (D&C Optimization).
• On the plane: closest pair, Delaunay triangulation, convex hull by merging.

Classic D&C algorithms

Algorithm	Recurrence	Time
merge sort, inversion count	$2T(n/2)+n$	$O(n\log n)$
closest pair of points	$2T(n/2)+n$ (presorted by $y$ via merging)	$O(n\log n)$
Karatsuba multiplication	$3T(n/2)+n$	$O(n^{1.585})$
Strassen	$7T(n/2)+n^2$	$O(n^{2.807})$
FFT	$2T(n/2)+n$	$O(n\log n)$
median of medians	$T(n/5)+T(7n/10)+n$	$O(n)$
maximum subarray (as a D&C)	$2T(n/2)+1$ with a 4-value summary	$O(n)$
skyline / union of rectangles in 1D	merge two skylines	$O(n\log n)$
polynomial multipoint evaluation	product tree, remainder tree	$O(n{\log }^{2}n)$

This is the master theorem (restricted to polynomial $f(n)=c{n}^d$, which covers every row above; Complexity and Analysis states the fully general $f(n)$ version and the non-polynomial Akra–Bazzi extension).

Proof: the recursion-tree bound for $T(n)=aT(n/b)+c{n}^d$

At recursion depth $k$ there are $a^k$ subproblems, each of size $n/b^k$, so the non-recursive work at that depth totals $a^k\cdot c(n/b^k{)}^d=c{n}^d\cdot {\rho }^k$ where $\rho =a/b^d$. Summing over the ${\log }_{b}n$ depths of the tree:

• If $\rho <1$: the geometric series ${\sum }_k{\rho }^k$ converges to a constant, so the total is dominated by the root term, $\Theta (n^d)$.
• If $\rho =1$: every depth contributes exactly $c{n}^d$, and there are $\Theta ({\log }_{b}n)$ depths, giving $\Theta (n^d\log n)$. This is the merge sort / FFT case ($a=b=2$, $d=1$: $\rho =1$).
• If $\rho >1$: the series is dominated by the deepest term, depth ${\log }_{b}n$, giving $\Theta ((c{n}^d){\rho }^{{\log }_{b}n})=\Theta (n^{{\log }_{b}a})$ (since ${\rho }^{{\log }_{b}n}=(a/b^d{)}^{{\log }_{b}n}=n^{{\log }_{b}a}/n^d$). This is the Karatsuba case ($a=3,b=2,d=1$: $\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$) and the Strassen case ($a=7,b=2,d=2$: $\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})$).
  $■$

Proof: median of medians is $O(n)$

This recurrence has an unequal split, $T(n)\le T(n/5)+T(7n/10)+cn$ (finding the pivot recurses on $n/5$ medians-of-5; partitioning around it recurses on at most $7n/10$ elements, since the pivot is guaranteed greater than at least $3$ elements in each of at least half the groups of 5, and symmetrically less than at least $3$ in the other half, eliminating $\ge 3n/10$ elements). The two branch sizes sum to $n/5+7n/10=9n/10<n$, i.e. a fixed fraction $r=9/10<1$ of $n$. By induction, assume $T(m)\le Kcm$ for all $m<n$ (some constant $K$ to be fixed): then $T(n)\le Kc(n/5)+Kc(7n/10)+cn=Kc\cdot (9n/10)+cn=cn(0.9K+1)$. Choosing $K$ with $0.9K+1\le K$, i.e. $K\ge 10$, closes the induction, giving $T(n)=O(n)$. $■$