= CDQ divide and conquer
{c}
<CDQ divide and conquer> is an offline divide-and-conquer pattern that partitions items in one ordered <dimension>, solves each half recursively and counts or applies contributions from the left half to the right during a merge. For three-dimensional dominance <counting>, first order by one coordinate, then merge by a second while a <Fenwick tree> aggregates the third. The cross-half pass accounts for interactions not handled inside either recursive call. Tie conventions must match strict or non-strict comparisons, and temporary updates must be removed or isolated before unrelated subproblems. A common implementation takes $O(n\log^2n)$ time after coordinate compression.
Back to article page
