Offline Divide-and-Conquer over Time (CDQ Divide-and-Conquer for 3D Partial Orders)

What Is CDQ Divide-and-Conquer?

Popularized by IOI gold medalist Chen Danqi (CDQ) in 2008 (and rooted in Bentley's 1980 multidimensional divide-and-conquer), CDQ Divide-and-Conquer is an offline technique that eliminates one dimension of a multidimensional query problem (or eliminates the "time" dimension of a dynamic update-and-query problem) by recursing on array halves $[lo, mid)$ and $[mid, hi)$ and computing only the cross-half contribution where left-half elements update right-half elements.

The Canonical Problem: 3D Partial Order (3D Dominance Counting)

Given $N$ points $P_i = (x_i, y_i, z_i)$ in $\mathbb{R}^3$ (with coordinates compressed to $[1, N]$), for each point $j$ we want to count how many points $i \neq j$ satisfy:

Let's see how each dimension is systematically neutralized:

1. Dimension 1 ($X$-Coordinate) — Initial Presort: Sort all points lexicographically by $(x, y, z)$ and collapse identical points $(x, y, z)$ into weighted unique points. Now, throughout the entire recursion on $[lo, hi)$, every point in the left half $i \in [lo, mid)$ is guaranteed to satisfy $x_i \le x_j$ for every point in the right half $j \in [mid, hi)$!
2. Dimension 2 ($Y$-Coordinate) — Two-Pointer Merge: Assume recursively that $[lo, mid)$ and $[mid, hi)$ are sorted by $Y$. Sweep pointer $p_L$ across $[lo, mid)$ and pointer $p_R$ across $[mid, hi)$ in ascending $Y$-order. Whenever $P[p_L].y \le P[p_R].y$, advance $p_L$; otherwise advance $p_R$. At the moment we process $p_R$, every left-half point already passed by $p_L$ satisfies both $x_i \le x_j$ and $y_i \le y_j$!
3. Dimension 3 ($Z$-Coordinate) — 1D Fenwick Tree (BIT): When advancing $p_L$, insert its $Z$-coordinate into a 1D Fenwick Tree: bit.add(P[p_L].z, P[p_L].weight). When advancing $p_R$, query prefix sum bit.query(P[p_R].z) to count how many active left-half points also satisfy $z_i \le z_j$! Finally, rollback the Fenwick tree by subtracting only the touched $P[p_L].z$ entries in $O(hi - lo)$ time.

Production C++20 Implementation: 3D Dominance Counting via CDQ Divide-and-Conquer

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <vector>

struct Point3D {
    int x, y, z;
    int weight;   // Multiplicity of identical (x, y, z) points
    int dom_cnt;  // Number of points dominated by this unique point
    int orig_id;
};

class FenwickTree {
public:
    explicit FenwickTree(std::size_t max_z) : tree_(max_z + 1, 0) {}

    void add(int idx, int delta) noexcept {
        for (std::size_t i = static_cast<std::size_t>(idx); i < tree_.size(); i += i & (~i + 1)) {
            tree_[i] += delta;
        }
    }

    int query(int idx) const noexcept {
        int sum = 0;
        for (std::size_t i = static_cast<std::size_t>(idx); i > 0; i &= i - 1) {
            sum += tree_[i];
        }
        return sum;
    }

private:
    std::vector<int> tree_;
};

// Solves 3D Partial Order (1 <= z_i <= max_z) in O(N log^2 N) time and O(N) space.
// Returns for each unique point the total weight of other points it dominates.
void solve_3d_dominance_cdq(std::vector<Point3D>& pts, int max_z) {
    if (pts.empty()) return;

    // 1. Sort lexicographically by (x, y, z)
    std::sort(pts.begin(), pts.end(), [](const Point3D& a, const Point3D& b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        return a.z < b.z;
    });

    // 2. Deduplicate identical (x, y, z) triples and accumulate multiplicity weight
    std::vector<Point3D> uniq;
    uniq.reserve(pts.size());
    for (const auto& p : pts) {
        if (!uniq.empty() && uniq.back().x == p.x &&
            uniq.back().y == p.y && uniq.back().z == p.z) {
            uniq.back().weight += p.weight;
        } else {
            uniq.push_back(p);
        }
    }

    const std::size_t m = uniq.size();
    std::vector<Point3D> scratch(m);
    FenwickTree bit(static_cast<std::size_t>(max_z));

    auto cdq = [&](auto& self, std::size_t lo, std::size_t hi) -> void {
        if (hi - lo <= 1) return;
        const std::size_t mid = lo + (hi - lo) / 2;

        self(self, lo, mid);
        self(self, mid, hi);

        // Both [lo, mid) and [mid, hi) are now sorted by Y.
        // Merge them by Y while applying left-half BIT updates to right-half queries.
        std::size_t pL = lo, pR = mid, out = lo;
        while (pL < mid && pR < hi) {
            if (uniq[pL].y <= uniq[pR].y) {
                bit.add(uniq[pL].z, uniq[pL].weight);
                scratch[out++] = uniq[pL++];
            } else {
                uniq[pR].dom_cnt += bit.query(uniq[pR].z);
                scratch[out++] = uniq[pR++];
            }
        }
        while (pR < hi) {
            uniq[pR].dom_cnt += bit.query(uniq[pR].z);
            scratch[out++] = uniq[pR++];
        }
        // Rollback Fenwick tree for all left-half elements that were inserted!
        for (std::size_t i = lo; i < pL; ++i) {
            bit.add(uniq[i].z, -uniq[i].weight);
        }
        while (pL < mid) {
            scratch[out++] = uniq[pL++];
        }

        std::copy(scratch.begin() + lo, scratch.begin() + hi, uniq.begin() + lo);
    };

    cdq(cdq, 0, m);

    // Account for self-dominance among identical (x, y, z) duplicates
    for (auto& u : uniq) {
        u.dom_cnt += (u.weight - 1);
    }
    pts = std::move(uniq);
}