Pattern Guide
CDQ Divide and Conquer
"Solve 3D partial order problems offline. Process left half, measure cross contributions."
CDQ (陈丹琦) divide and conquer solves offline problems where answer for query q depends on all operations before q. Recursively: (1) solve left half, (2) compute contribution of left half on right half, (3) solve right half. This reduces a 3D problem (time, x, y) to 2D by sorting time, then processing cross-contributions with merge sort + Fenwick tree. O(n log²n) for 3D partial order.
Problems you can solve with this pattern
3 problems · click any to start solving
// 3D partial order: for each point (t,x,y), count points with t'<t, x'<=x, y'<=y
// CDQ: time dimension handled by divide (left half has smaller t)
// x dimension: sort + two-pointer
// y dimension: Fenwick tree
function cdq3D(points) { // points = [{t, x, y, idx}] sorted by t
const ans = new Array(points.length).fill(0);
const n = points.length;
const bit = new Array(n + 1).fill(0);
const upd = i => { for (; i <= n; i += i & (-i)) bit[i]++; };
const qry = i => { let s = 0; for (; i > 0; i -= i & (-i)) s += bit[i]; return s; };
const undo = [];
function solve(l, r) {
if (l === r) return;
const mid = (l + r) >> 1;
solve(l, mid); // process left half
// Compute contribution of left half on right half
const left = points.slice(l, mid + 1).sort((a, b) => a.x - b.x);
const right = points.slice(mid + 1, r + 1).sort((a, b) => a.x - b.x);
let li = 0;
for (const rp of right) {
while (li < left.length && left[li].x <= rp.x) {
upd(left[li].y); undo.push(left[li].y); li++;
}
ans[rp.idx] += qry(rp.y);
}
// Undo BIT updates
while (undo.length) { const y = undo.pop(); for (let i = y; i <= n; i += i & (-i)) bit[i]--; }
solve(mid + 1, r); // process right half
}
solve(0, n - 1);
return ans;
}CDQ D&C solves problems of the form: "for each query point, count preceding points that dominate it in multiple dimensions." The time dimension is free (guaranteed: left half precedes right half). CDQ recursively processes: left half → compute left-on-right contributions → right half. The cross contribution step: sort both halves by x, use two pointers + Fenwick tree on y to count 2D domination. Result: O(n log²n).
// 3D partial order: for each point (t,x,y), count points with t'<t, x'<=x, y'<=y
// CDQ: time dimension handled by divide (left half has smaller t)
// x dimension: sort + two-pointer
// y dimension: Fenwick tree
function cdq3D(points) { // points = [{t, x, y, idx}] sorted by t
const ans = new Array(points.length).fill(0);
const n = points.length;
const bit = new Array(n + 1).fill(0);
const upd = i => { for (; i <= n; i += i & (-i)) bit[i]++; };
const qry = i => { let s = 0; for (; i > 0; i -= i & (-i)) s += bit[i]; return s; };
const undo = [];
function solve(l, r) {
if (l === r) return;
const mid = (l + r) >> 1;
solve(l, mid); // process left half
// Compute contribution of left half on right half
const left = points.slice(l, mid + 1).sort((a, b) => a.x - b.x);
const right = points.slice(mid + 1, r + 1).sort((a, b) => a.x - b.x);
let li = 0;
for (const rp of right) {
while (li < left.length && left[li].x <= rp.x) {
upd(left[li].y); undo.push(left[li].y); li++;
}
ans[rp.idx] += qry(rp.y);
}
// Undo BIT updates
while (undo.length) { const y = undo.pop(); for (let i = y; i <= n; i += i & (-i)) bit[i]--; }
solve(mid + 1, r); // process right half
}
solve(0, n - 1);
return ans;
}1. If base case, return
2. cdq(left half)
3. Compute left→right cross contributions (sorted by 2nd dim, BIT on 3rd dim)
4. Undo BIT changes
5. cdq(right half)
Key insight: The 1st dimension (time) is handled by divide — left half always precedes right. Reduce 3D to 2D using sort + BIT.
Applications:
- 3D partial order: O(n log²n)
- Dynamic inversion counting: O(n log²n)
- Offline range k-th smallest: O(n log²n)
- Any problem reducible to "count preceding points satisfying multi-dim constraints"
vs Persistent Segment Tree: Both solve offline range queries but with different constant factors. CDQ is cache-friendlier; PST uses O(n log n) extra space.