ii. CDQ Divide and Conquer

CDQ (after Chen Danqi) divides the sequence of operations in half, recurses on both halves, and lets the left half’s updates act on the right half’s queries. Every update/query pair interacts at exactly one level. This removes one dimension at the cost of a $\log$ factor, with only $O(n)$ memory.

Proof: every (earlier update, later query) pair interacts at exactly one level

Fix an update at position $i$ and a query at position $j$ with $i<j$ (an update only affects queries later in the fixed first dimension, by the problem’s own ordering). At the root call, either both land in the same half — recursion continues, and by induction the same argument applies one level down with a strictly smaller range — or $i$ is in the left half and $j$ in the right half, in which case the merge step at this exact call applies $i$‘s update to $j$‘s query, and this call never recurses on a range containing both again. So the pair is handled at the unique level where they first separate: not zero times, since a singleton range cannot contain both, forcing eventual separation; not more than once, since once separated into different child calls, no later call’s range contains both again. $■$

3D partial order

For $n$ points $(a,b,c)$, count for each point how many points have $a^{\prime }\le a$, $b^{\prime }\le b$, $c^{\prime }\le c$ (CSES-style “3D dominance”).

1. Sort by $a$ (ties broken by $b$, then $c$). Merge identical points first and give them multiplicities, otherwise equal points count each other inconsistently.
2. CDQ on the index: after recursing, merge the halves by $b$. Left elements insert $c$ into a BIT, right elements query.
3. Undo the BIT insertions (don’t clear the whole BIT).

struct P { int a, b, c, cnt, id; };
vector<P> p; vector<ll> res; BIT bit;
void cdq(int l, int r) {                         // [l, r), p sorted by a
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    cdq(l, m); cdq(m, r);                        // both halves are now sorted by b
    int i = l;
    for (int j = m; j < r; j++) {
        for (; i < m && p[i].b <= p[j].b; i++) bit.add(p[i].c, p[i].cnt);
        res[p[j].id] += bit.sum(p[j].c);
    }
    for (int k = l; k < i; k++) bit.add(p[k].c, -p[k].cnt);
    inplace_merge(p.begin() + l, p.begin() + m, p.begin() + r, [](auto& x, auto& y) { return x.b < y.b; });
}

$O(n{\log }^{2}n)$ time, $O(n)$ memory. Point $j$ also dominates its own duplicates: add cnt - 1 to its answer after merging duplicates.

Proof: $O(n{\log }^{2}n)$ time, $O(n)$ memory

The recursion itself is standard divide and conquer with $T(n)=2T(n/2)+O(n\log n)$ (the merge step scans both halves with two pointers, $O(n)$, but each BIT operation inside costs $O(\log n)$, and there are $O(n)$ of them per merge) — by the recursion-tree argument ($a=b=2$, $d=1$ on top of the extra $\log$ factor folded into $c$), this solves to $O(n{\log }^{2}n)$. Memory is $O(n)$ because the BIT is a single array of size $O(\max c)$ shared across all recursive calls (undone after each merge rather than rebuilt), and inplace_merge uses $O(1)$ extra space (or $O(n)$ scratch allocated once, not per call). $■$

Removing time from dynamic problems

Treat the operation index as the first dimension. “Point updates and rectangle-sum queries, interleaved”: updates in the left half of time affect queries in the right half. Inside the merge, sweep by $x$ with a BIT over $y$. That gives $O(n{\log }^{2}n)$ with $O(n)$ memory, instead of a 2D segment tree or BIT of BITs ($O(n{\log }^{2}n)$ memory).

The pattern works whenever:

• contributions are additive (or otherwise mergeable) across updates;
• an update affects a query iff it comes earlier in time and satisfies a static (time-independent) condition.

CDQ for DP

When $d{p}_i$ depends on $d{p}_j$ for $j<i$ with a condition needing a data structure (2D dominance, convex hull with non-monotone slopes), the values aren’t known in time for a simple sweep. Process in-order:

1. cdq(l, m): left $dp$ values become final.
2. Apply the transitions from $[l,m)$ to $[m,r)$ (sort both halves, sweep with a structure).
3. cdq(m, r).

Note the order differs from counting: the right half is recursed after the cross step. Examples: 3D LIS (longest chain in $(a,b,c)$ partial order), DP with convex hull trick where slopes and query points come in arbitrary order (build the hull of the left half, query it with the right half’s points sorted).

Higher dimensions

Nest: CDQ inside CDQ removes one more dimension each time, $O(n{\log }^{k-1}n)$ for $k$ dimensions. Beyond 4D, bitset approaches ($O(n^{2}k/64)$: one bitset per dimension and value threshold, AND them together) or KD-trees are usually simpler.

Proof: nesting gives $O(n{\log }^{k-1}n)$ for $k$ dimensions

By induction on $k$. For $k=2$ dimensions, sorting by the first and sweeping with a BIT over the second is $O(n\log n)=O(n{\log }^{k-1}n)$ with $k-1=1$, the base case. For $k$ dimensions, outer CDQ on dimension 1 (vs. dimension 2, the merge step) costs $T(n)=2T(n/2)+O(f(n))$ where $f(n)$ is the cost of resolving the remaining $k-1$ dimensions at each merge — by the inductive hypothesis $f(n)=O(n{\log }^{k-2}n)$. Substituting into the recursion-tree bound (ρ = 1 case, since $a=b=2$): each of the $O(\log n)$ depths contributes $O(n{\log }^{k-2}n)$ total work (summed over that depth’s subproblems, since work is linear-ish per level by the standard D&C accounting), giving $O(n{\log }^{k-2}n\cdot \log n)=O(n{\log }^{k-1}n)$. $■$

Alternatives

Problem	CDQ	Other
2D dominance (static)	unnecessary	sort + BIT sweep
3D dominance	$O(n{\log }^{2}n)$, $O(n)$ memory	BIT of sorted vectors $O(n{\log }^{2}n)$; KD-tree $O(n\sqrt{n})$
point update + rectangle query	$O(n{\log }^{2}n)$ offline	2D BIT with compression; online: BIT of treaps or wavelet structures
dynamic CHT	CDQ + static hull per level	Li Chao tree (usually easier)

Pitfalls

• Ties: decide which equal coordinates count as dominated and enforce it in both the initial sort and the merge comparison.
• Undo the structure exactly; clearing an $O(n)$ BIT per call makes it $O(n^2)$.
• Keep the merge stable, and make sure step order (recurse right before or after the cross step) matches counting or DP.

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 outright, or a persistent segment tree answers it more directly — any of the three is less code than CDQ when it applies.