CDQ Divide and Conquer

Divide the query timeline in half; recurse on both halves; then apply the left half’s updates to the right half’s queries. It reduces a $k$ -dimensional partial-order counting problem to a $(k - 1)$ -dimensional one, at the cost of a $lo g$ factor.

The skeleton

// operations are sorted by TIME; each is either an update or a query
void cdq(int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    cdq(lo, mid);
    cdq(mid, hi);
    // now: apply updates in [lo, mid) to queries in [mid, hi)
    //      typically a merge by the second dimension, with a BIT on the third
    mergeAndApply(lo, mid, hi);
}

The recursion handles interactions within each half; the merge handles interactions across the split. Every pair of operations is considered exactly once, at the level where they are separated.

The canonical use: 3D partial order

“Given $n$ triples $(a, b, c)$ , for each one count how many others have $a^{'} \leq a$ , $b^{'} \leq b$ , $c^{'} \leq c$ .”

Sort by $a$ — the first dimension is handled by the initial sort.
CDQ on the index (which now represents $a$ -order) — the second dimension is handled by merging both halves by $b$ .
BIT over $c$ — the third dimension.

void cdq(int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    cdq(lo, mid); cdq(mid, hi);
 
    // merge [lo,mid) and [mid,hi) by b; left elements are UPDATES, right are QUERIES
    int i = lo, j = mid;
    while (j < hi) {
        while (i < mid && p[i].b <= p[j].b) { bit.add(p[i].c, 1); i++; }
        ans[p[j].id] += bit.query(p[j].c);
        j++;
    }
    while (--i >= lo) bit.add(p[i].c, -1);                // roll back the BIT
    inplace_merge(p.begin()+lo, p.begin()+mid, p.begin()+hi, byB);
}

$O (n lo g^{2} n)$ . Rolling back the BIT (rather than clearing it) keeps the complexity right.

Dynamic problems made static

The other main use: turn a problem with updates into one without.

“Point updates and rectangle-sum queries, both online in time.”

Treat time as the first dimension.
CDQ on time: updates in the left half affect queries in the right half.
Within the merge, sort by $x$ and use a BIT over $y$ .

$O (n lo g^{2} n)$ — the standard alternative to a 2D segment tree or a persistent structure, with far less memory.

CDQ vs the alternatives

Problem	CDQ	Alternative
3D partial order counting	$O (n lo g^{2} n)$	KD-tree $O (n n)$ ; BIT-of-BITs $O (n lo g^{2} n)$ memory-heavy
Point update + 2D range query	$O (n lo g^{2} n)$	2D segment tree, more memory
Dynamic convex hull / CHT	CDQ + hull per level	Li Chao
DP with “future depends on past” transitions	CDQ on the DP index	direct DP if the order allows
Counting inversions	trivially, but a plain BIT is simpler
$k$ -dimensional order, $k \geq 4$	nested CDQ, $O (n lo g^{k - 1} n)$	KD-tree

CDQ for DP

When a DP transition $d p [i] \leftarrow f (d p [j])$ for $j < i$ requires a data structure that itself depends on $d p [j]$ , ordinary sweeping fails (the values are not known when needed). CDQ resolves it:

Recurse on the left half — those $d p$ values become final.
Apply the left half’s contributions to the right half’s states.
Recurse on the right half.

This is how “DP + convex hull trick with non-monotone slopes” and “DP + 2D dominance” problems are solved.

Practical notes

Sort once at the top by the first dimension; the recursion then re-sorts only by the second (with inplace_merge, keeping it $O (n lo g n)$ per level).
Roll back auxiliary structures instead of clearing them.
Handle ties carefully — equal values in a dimension need a consistent tiebreak, or you will count some pairs twice and others not at all.
Deduplicate identical triples first if the problem counts them together.

When not to use it

CDQ has a real constant factor and is fiddly to debug. Before writing it, check whether:

a plain offline sweep with one BIT suffices (two dimensions only);
the queries can be sorted to remove a dimension;
a persistent segment tree answers it more directly.

whoashish's cp notes

Directory