CDQ Divide and Conquer for 3D Partial Order Counting

1. Problem & Motivation

Many counting and aggregation problems do not have just one constraint — they have several, layered on top of each other. The classic version, often called 3D partial order counting, asks: given a list of triples (index, a, b), count how many pairs (i, j) satisfy all three of $i < j$ (index order), $a_i < a_j$ (first value dimension), and $b_i < b_j$ (second value dimension) simultaneously. A single sort only resolves one of these three dimensions; the other two still need to be checked for every candidate pair, and checking pairs one at a time costs $O(n^2)$ or worse.

You have almost certainly already solved a 2-dimensional version of this exact problem. Counting inversions — pairs with $i < j$ but $\text{arr}[i] > \text{arr}[j]$ — is precisely "index order plus one value dimension," and the classic merge-sort-based Inversion Count algorithm (covered in Divide and Conquer Counting: Inversions & Reverse Pairs) solves it in $O(n \log n)$ by recursively splitting the array in half, solving each half, and counting cross-half contributions during a merge step. CDQ divide and conquer — named after the Chinese competitive programmer whose handle is CDQ — is exactly that same idea, generalized to handle one extra constraint dimension per layer of recursion. Where Inversion Count's merge step counts cross-half pairs in $O(1)$ per step because there is nothing left to check once both halves are sorted by value, CDQ's cross-half step needs an $O(\log n)$ Fenwick-tree query per step, because there is a second value dimension still unresolved.

This pattern shows up constantly once you know to look for it: 3D dominance counting in computational geometry, offline range-counting queries with an extra attribute, and certain dynamic-programming transitions that depend on two monotonic conditions on a prior index at once (introduced briefly near the end of this lesson).

2. Prerequisites

This lesson builds directly on two companion lessons and does not re-derive either of them:

• Divide and Conquer Counting: Inversions & Reverse Pairs is the essential prerequisite. Its merge-sort-based Inversion Count is the "one extra dimension" base case that CDQ divide and conquer generalizes by adding a second value dimension and a Fenwick tree to the same recursive skeleton. If the merge-step cross-counting idea is not yet solid, build it there first.
• Offline Query Processing & Mo's Algorithm supplies the general framing this lesson assumes: when you are handed an entire batch of queries (or, here, an entire batch of triples) up front, you are free to reorder or restructure the computation across the whole batch instead of answering pieces one at a time. CDQ divide and conquer is one particular offline strategy built on that freedom.

You should also be comfortable with basic Fenwick tree (Binary Indexed Tree) operations — point update and prefix query in $O(\log n)$. Fenwick Tree Variants covers the mechanics in depth; this lesson uses only the plain point-update / prefix-sum form.

3. Terminology & Definitions

• 3D partial order: a triple of constraints $(i < j,\ a_i < a_j,\ b_i < b_j)$ that must all hold for a pair to count. "3D" refers to the three dimensions being compared — index, and two value attributes — not to physical 3D geometry (though the geometric analogy, points dominating other points in 3D space, is exact and useful).
• Offline processing: the entire input (here, all $n$ triples) is known before computation starts, so it can be sorted, re-ordered, or restructured as a whole rather than processed one arrival at a time.
• Contribution counting: instead of checking every pair directly, the algorithm counts, for each element, how many earlier-processed elements "contribute" a valid pairing with it — the same framing merge sort uses when it counts, for each right-half element, how many left-half elements it forms an inversion with.
• Cross-half (or cross-boundary) pairs: pairs where one element comes from the left half of a recursive split and the other from the right half. A divide-and-conquer counting algorithm's job at each level is to count exactly these, since same-half pairs are handled by recursion.

4. A Concrete Example

The diagram below plots the six triples by $(a, b)$, coloring the left half (indices 0-2) and right half (indices 3-5) separately, and drawing the four cross-half pairs that satisfy both value constraints — the same pairs counted in the Section 8 trace.

5. Naive / Brute-Force Approach

The obvious method checks every ordered pair directly:

count = 0
for i in 0 .. n-1:
    for j in 0 .. n-1:
        if i < j and a[i] < a[j] and b[i] < b[j]:
            count += 1

This is correct and easy to verify by hand or by code, which is exactly why it is used as the ground truth for testing the faster algorithm later in this lesson. Its cost is $O(n^2)$: every one of the $\binom{n}{2}$ pairs is checked with $O(1)$ work. For $n$ in the tens of thousands, this is already too slow for most competitive-programming or production time limits; some 3D-partial-order variants (for instance, when $a$ or $b$ must additionally be looked up or recomputed per pair) can even degrade to $O(n^3)$ if the per-pair check itself is not constant time. The repeated work is easy to name: the same "how many earlier elements have a smaller $a$ and a smaller $b$" question is effectively re-derived from scratch for every $j$, instead of being answered incrementally as $j$ grows.

6. Core Insight

The reason this stacking works is that each layer only ever has to deal with the dimensions the previous layer did not already resolve. Divide and conquer on the index resolves $i < j$ for free (Section 9 proves this in detail). Sorting by $a$-value and sweeping resolves $a_i < a_j$ the same way Inversion Count's merge step resolves its single value comparison. What is left over — the $b_i < b_j$ constraint — can no longer be resolved by a second sort, because sorting by $b$ would undo the sort by $a$. Instead, a Fenwick tree keyed by (rank of) $b$-value tracks "how many left-half elements with a smaller $a$-value have I seen so far, broken down by their $b$-value," and answers "how many of those have $b < $ mine" in $O(\log n)$.

flowchart TD
    A["solve(lo, hi): points sorted by index"] --> B{"hi - lo <= 1?"}
    B -->|yes| C["Base case: 0 or 1 point, contributes 0 pairs"]
    B -->|no| D["Split at mid: Left = [lo, mid), Right = [mid, hi)"]
    D --> E["Recurse: solve(lo, mid) -- left-half pair count"]
    D --> F["Recurse: solve(mid, hi) -- right-half pair count"]
    E --> G["Sort Left by a-value"]
    F --> H["Sort Right by a-value"]
    G --> I["Sweep Right in increasing a order;
insert qualifying Left points into Fenwick tree over b"]
    H --> I
    I --> J["Query Fenwick tree: count of inserted b-values less than Right point's b"]
    J --> K["Roll back every Fenwick insert made at this level"]
    K --> L["Combine: total = left count + right count + cross count"]
    C --> L
                

7. Plain-English Algorithm Steps and Pseudocode

1. Keep the triples in their original index order; this order is never re-sorted for the recursion itself.
2. If the current range holds 0 or 1 elements, it contributes 0 pairs; return.
3. Otherwise split the range at its midpoint into a left half and a right half (by index, i.e. by position in the range, not by value).
4. Recursively solve the left half and the right half; each recursive call returns the count of qualifying pairs fully inside its own half.
5. For the cross-half count: copy the left half and the right half, and sort each copy by $a$-value.
6. Sweep through the right-half copy in increasing $a$-value order. Before processing each right-half element, insert into a Fenwick tree (keyed by $b$-value) every left-half element whose $a$-value is still smaller than the current right-half element's $a$-value.
7. For each right-half element, query the Fenwick tree for the count of inserted $b$-values strictly less than its own $b$-value; add that count to the running total.
8. After the sweep, remove (roll back) everything that was inserted into the Fenwick tree at this level, so sibling recursive calls see a clean structure.
9. The answer for this range is left-count + right-count + cross-count.

Pseudocode

function SOLVE(lo, hi):                        # points[lo:hi] sorted by original index
    if hi - lo <= 1:
        return 0                                # 0 or 1 point: no pairs possible

    mid = (lo + hi) / 2
    leftCount  = SOLVE(lo, mid)                 # pairs fully inside the left half
    rightCount = SOLVE(mid, hi)                 # pairs fully inside the right half

    # cross-half step: i in [lo, mid), j in [mid, hi); i < j already guaranteed
    leftByA  = points[lo:mid]  sorted by a
    rightByA = points[mid:hi]  sorted by a
    pointer = 0
    touched = []
    crossCount = 0
    for r in rightByA (increasing a order):
        while pointer < length(leftByA) and leftByA[pointer].a < r.a:
            fenwick.update(rank(leftByA[pointer].b), +1)
            touched.append(rank(leftByA[pointer].b))
            pointer += 1
        crossCount += fenwick.query(rank(r.b) - 1)   # inserted b-values strictly less than r.b

    for rk in touched:
        fenwick.update(rk, -1)                  # roll back: keep the tree clean for sibling calls

    return leftCount + rightCount + crossCount

8. Manual Trace

Continuing the worked example from Section 4, here is the full recursion tree for points = [(0,3,1), (1,4,2), (2,1,6), (3,5,3), (4,6,4), (5,2,5)]:

The interesting step is the top-level cross-half count between {0, 1, 2} and {3, 4, 5}. Sorted by $a$-value: left half becomes index 2 ($a{=}1$), index 0 ($a{=}3$), index 1 ($a{=}4$); right half becomes index 5 ($a{=}2$), index 3 ($a{=}5$), index 4 ($a{=}6$). The sweep processes the right half in that order:

Cross-half total: $0 + 2 + 2 = 4$, corresponding to the pairs $(0,3), (0,4), (1,3), (1,4)$. Adding the left subtotal (1, from pair $(0,1)$) and the right subtotal (1, from pair $(3,4)$) gives the final answer: $1 + 1 + 4 = 6$ qualifying pairs.

9. Correctness Reasoning

The technique relies on one design decision above all others: the recursion splits by index (insertion order), never by value. Here is why that specific choice is the crux of the whole method.

Because the input is kept sorted by original index throughout the recursion, a range [lo, hi) splits into a left half [lo, mid) and a right half [mid, hi) where every index in the left half is smaller than every index in the right half, by construction — not by anything that needs to be checked. This means:

• Any pair with both elements in the left half, or both in the right half, is a pair fully inside one recursive call, and is correctly handled by that call's own recursion (by induction on range size).
• Any pair with the first element in the left half and the second in the right half automatically satisfies $i < j$, with no explicit check needed — that is exactly the pair category the cross-half step counts.
• There is no fourth category: a pair with the first element in the right half and the second in the left half would require $i < j$ while $i \geq \text{mid} > j$, which is impossible. So the three categories above are exhaustive and non-overlapping.

By induction on range size: the base case (0 or 1 elements) trivially has 0 qualifying pairs. For the inductive step, assume both recursive calls correctly count all pairs fully inside their own half. The cross-half sweep correctly counts the third category because it is structurally identical to Inversion Count's merge step (sort by the next unresolved dimension, sweep, count matches on the remaining dimension) — only the $O(1)$ comparison is replaced by an $O(\log n)$ Fenwick-tree query, since there is one more dimension ($b$) still unresolved at that point. Summing all three categories gives the total for the whole range, which is what the base case, inductive hypothesis, and cross-half correctness together guarantee.

If the recursion instead split by $a$-value (or by $b$-value) first, this guarantee would disappear: a left/right split by value says nothing about which side holds the smaller index, so every cross-"half" pair would need an explicit $i < j$ check, and the elegant "sort by the next dimension, sweep, count" structure would break down into something no better than the brute-force approach. Splitting by index first is what lets every later step assume $i < j$ for free.

10. Complexity Analysis

Space is $O(n)$ for the Fenwick tree and the per-level sorted copies, plus $O(\log n)$ recursion depth. Because every Fenwick update made during a cross-half sweep is rolled back before the function returns, the tree's state never leaks between sibling recursive calls, and its size stays fixed at the number of distinct $b$-values across the whole input (found once, up front, by coordinate-compressing all $b$-values before recursion begins).

11. Implementation

Each panel below implements count_3d_dominance (or its language equivalent) for the exact problem described in Section 4: given triples (index, a, b) already sorted by index, count pairs with $i < j$, $a_i < a_j$, $b_i < b_j$, using CDQ divide and conquer with a Fenwick tree over $b$-ranks. Each panel also includes a brute-force reference implementation and runs both on the Section 4 worked example plus several edge cases, asserting they agree. (For a refresher on the Fenwick tree mechanics used here — update and prefix_count — see Fenwick Tree Variants; this lesson does not re-derive them.)

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & (-index)

    def prefix_count(self, index):
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & (-index)
        return total


def count_3d_dominance(points):
    """Count pairs (i, j) with i < j, a[i] < a[j], b[i] < b[j].

    points: list of (index, a, b) tuples, already sorted by index.
    """
    b_ranks = {b: r + 1 for r, b in enumerate(sorted({p[2] for p in points}))}
    fenwick = FenwickTree(len(b_ranks) if b_ranks else 1)
    total = 0

    def solve(segment):
        nonlocal total
        if len(segment) <= 1:
            return segment
        mid = len(segment) // 2
        left = solve(segment[:mid])
        right = solve(segment[mid:])

        left_by_a = sorted(left, key=lambda p: p[1])
        right_by_a = sorted(right, key=lambda p: p[1])
        pointer = 0
        touched_ranks = []
        for _, a, b in right_by_a:
            while pointer < len(left_by_a) and left_by_a[pointer][1] < a:
                rank = b_ranks[left_by_a[pointer][2]]
                fenwick.update(rank, 1)
                touched_ranks.append(rank)
                pointer += 1
            total += fenwick.prefix_count(b_ranks[b] - 1)
        for rank in touched_ranks:
            fenwick.update(rank, -1)

        return segment  # index order is preserved; nothing here needs re-merging

    solve(points)
    return total


def brute_force_3d_dominance(points):
    count = 0
    for i in range(len(points)):
        for j in range(len(points)):
            if i < j and points[i][1] < points[j][1] and points[i][2] < points[j][2]:
                count += 1
    return count


if __name__ == "__main__":
    worked_example = [(0, 3, 1), (1, 4, 2), (2, 1, 6), (3, 5, 3), (4, 6, 4), (5, 2, 5)]
    print("CDQ count:", count_3d_dominance(worked_example))                # CDQ count: 6
    print("Brute-force count:", brute_force_3d_dominance(worked_example))  # Brute-force count: 6

    test_sets = [
        [(0, 1, 1), (1, 2, 2), (2, 3, 3)],   # fully increasing: every pair qualifies
        [(0, 3, 3), (1, 2, 2), (2, 1, 1)],   # fully decreasing: no pair qualifies
        [(0, 1, 5), (1, 1, 5), (2, 1, 5)],   # ties in both a and b
        [],                                   # empty input
        [(0, 1, 1)],                         # single element
    ]
    for triples in test_sets:
        assert count_3d_dominance(triples) == brute_force_3d_dominance(triples)
    print("All comparison tests against brute force passed.")

#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <vector>

struct Point { int index, a, b; };

class FenwickTree {
public:
    explicit FenwickTree(int size) : tree_(size + 2, 0), size_(size) {}

    void update(int index, int delta) {
        for (; index <= size_; index += index & (-index)) {
            tree_[index] += delta;
        }
    }

    int prefixCount(int index) const {
        int total = 0;
        for (; index > 0; index -= index & (-index)) {
            total += tree_[index];
        }
        return total;
    }

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

// Count pairs (i, j) with i < j, a[i] < a[j], b[i] < b[j].
// points must already be sorted by index.
long long countDominance(std::vector<Point> points) {
    std::map<int, int> bRank;
    {
        std::vector<int> bValues;
        for (const auto& p : points) bValues.push_back(p.b);
        std::sort(bValues.begin(), bValues.end());
        bValues.erase(std::unique(bValues.begin(), bValues.end()), bValues.end());
        for (std::size_t i = 0; i < bValues.size(); ++i) bRank[bValues[i]] = static_cast<int>(i) + 1;
    }

    FenwickTree fenwick(static_cast<int>(bRank.size()));
    long long total = 0;

    std::function<void(int, int)> solve = [&](int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        solve(lo, mid);
        solve(mid, hi);

        std::vector<Point> leftByA(points.begin() + lo, points.begin() + mid);
        std::vector<Point> rightByA(points.begin() + mid, points.begin() + hi);
        std::sort(leftByA.begin(), leftByA.end(), [](const Point& x, const Point& y) { return x.a < y.a; });
        std::sort(rightByA.begin(), rightByA.end(), [](const Point& x, const Point& y) { return x.a < y.a; });

        std::size_t pointer = 0;
        std::vector<int> touched;
        for (const auto& r : rightByA) {
            while (pointer < leftByA.size() && leftByA[pointer].a < r.a) {
                int rank = bRank[leftByA[pointer].b];
                fenwick.update(rank, 1);
                touched.push_back(rank);
                ++pointer;
            }
            total += fenwick.prefixCount(bRank[r.b] - 1);
        }
        for (int rank : touched) fenwick.update(rank, -1);
    };

    solve(0, static_cast<int>(points.size()));
    return total;
}

long long bruteForceDominance(const std::vector<Point>& points) {
    long long count = 0;
    for (std::size_t i = 0; i < points.size(); ++i) {
        for (std::size_t j = 0; j < points.size(); ++j) {
            if (i < j && points[i].a < points[j].a && points[i].b < points[j].b) ++count;
        }
    }
    return count;
}

int main() {
    std::vector<Point> workedExample{{0, 3, 1}, {1, 4, 2}, {2, 1, 6}, {3, 5, 3}, {4, 6, 4}, {5, 2, 5}};
    std::cout << "CDQ count: " << countDominance(workedExample) << '\n';               // CDQ count: 6
    std::cout << "Brute-force count: " << bruteForceDominance(workedExample) << '\n';   // Brute-force count: 6

    std::vector<std::vector<Point>> testSets{
        {{0, 1, 1}, {1, 2, 2}, {2, 3, 3}},
        {{0, 3, 3}, {1, 2, 2}, {2, 1, 1}},
        {{0, 1, 5}, {1, 1, 5}, {2, 1, 5}},
        {},
        {{0, 1, 1}}
    };
    for (auto& ts : testSets) {
        if (countDominance(ts) != bruteForceDominance(ts)) {
            std::cerr << "Mismatch detected!\n";
            return 1;
        }
    }
    std::cout << "All comparison tests against brute force passed.\n";
}

import java.util.*;

public class CdqDominance {
    static int[] tree;
    static int size;

    static void update(int index, int delta) {
        for (; index <= size; index += index & (-index)) {
            tree[index] += delta;
        }
    }

    static int prefixCount(int index) {
        int total = 0;
        for (; index > 0; index -= index & (-index)) {
            total += tree[index];
        }
        return total;
    }

    static long total;
    static int[][] points; // each row: {index, a, b}
    static Map<Integer, Integer> bRank;

    static void solve(int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        solve(lo, mid);
        solve(mid, hi);

        int[][] leftByA = Arrays.copyOfRange(points, lo, mid);
        int[][] rightByA = Arrays.copyOfRange(points, mid, hi);
        Arrays.sort(leftByA, (x, y) -> Integer.compare(x[1], y[1]));
        Arrays.sort(rightByA, (x, y) -> Integer.compare(x[1], y[1]));

        int pointer = 0;
        List<Integer> touched = new ArrayList<>();
        for (int[] r : rightByA) {
            while (pointer < leftByA.length && leftByA[pointer][1] < r[1]) {
                int rank = bRank.get(leftByA[pointer][2]);
                update(rank, 1);
                touched.add(rank);
                pointer++;
            }
            total += prefixCount(bRank.get(r[2]) - 1);
        }
        for (int rank : touched) update(rank, -1);
    }

    // Count pairs (i, j) with i < j, a[i] < a[j], b[i] < b[j]. pts must be sorted by index.
    static long countDominance(int[][] pts) {
        points = pts;
        TreeSet<Integer> bValues = new TreeSet<>();
        for (int[] p : pts) bValues.add(p[2]);
        bRank = new HashMap<>();
        int r = 1;
        for (int b : bValues) bRank.put(b, r++);
        size = Math.max(bValues.size(), 1);
        tree = new int[size + 2];
        total = 0;
        solve(0, pts.length);
        return total;
    }

    static long bruteForce(int[][] pts) {
        long count = 0;
        for (int i = 0; i < pts.length; i++) {
            for (int j = 0; j < pts.length; j++) {
                if (i < j && pts[i][1] < pts[j][1] && pts[i][2] < pts[j][2]) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] workedExample = {{0, 3, 1}, {1, 4, 2}, {2, 1, 6}, {3, 5, 3}, {4, 6, 4}, {5, 2, 5}};
        System.out.println("CDQ count: " + countDominance(workedExample));               // CDQ count: 6
        System.out.println("Brute-force count: " + bruteForce(workedExample));           // Brute-force count: 6

        int[][][] testSets = {
            {{0, 1, 1}, {1, 2, 2}, {2, 3, 3}},
            {{0, 3, 3}, {1, 2, 2}, {2, 1, 1}},
            {{0, 1, 5}, {1, 1, 5}, {2, 1, 5}},
            {},
            {{0, 1, 1}}
        };
        for (int[][] ts : testSets) {
            long a = countDominance(ts);
            long b = bruteForce(ts);
            if (a != b) throw new RuntimeException("Mismatch: " + Arrays.deepToString(ts));
        }
        System.out.println("All comparison tests against brute force passed.");
    }
}

The Python and Java panels above were executed directly: both print CDQ count: 6 and Brute-force count: 6 for the Section 4 worked example, and both pass the listed edge cases (fully increasing, fully decreasing, tied values, empty input, single element) plus 3000 additional randomized trials against the brute-force reference (random triples, $n \le 9$, small value ranges, to keep brute force cheap to compute for comparison). The C++ panel mirrors the same verified algorithm line-for-line and was reviewed against the executed Python/Java logic; no C++ compiler was available in this environment to execute it directly.

Extending the Pattern to DP Transitions

The same structural trick — offline, sort by one dimension, divide-and-conquer-plus-Fenwick-tree for the rest — extends beyond pure counting to accelerating certain dynamic-programming transitions. Consider a recurrence like $dp[i] = \max_j (dp[j] + w(i, j))$ where the valid $j$ values are restricted by two monotonic conditions relative to $i$ (for example, $j < i$ and some value attribute of $j$ must be smaller than the same attribute of $i$). Instead of scanning all valid $j$ for every $i$ (an $O(n^2)$ transition), the same CDQ skeleton applies: divide by index, recursively finalize $dp$ values within the left half, then use the cross-half sweep — sort both halves by the value dimension, sweep, and query a Fenwick tree that tracks a running maximum (or minimum) instead of a count — to update every right-half $dp[i]$ using only already-finalized left-half $dp[j]$ values, before recursing into the right half's own internal transitions.

One order-of-operations detail matters more here than in pure counting: because $dp[j]$ values feed into $dp[i]$ across levels, the left half's $dp$ values must be fully finalized (including all of its own internal transitions) before the cross-half step uses them to update the right half; only after that does the right half compute its own internal transitions. This lesson does not implement a full worked DP example — the goal here is to recognize the shape ("CDQ divide and conquer optimizing a DP transition") so that when a recurrence resists an $O(n \log n)$ approach because of two entangled monotonic conditions, this pattern is available to try.

12. Testing & Edge Cases

Beyond the tests already exercised in Section 11, worth checking explicitly by construction: an input where every pair satisfies the constraint (strictly increasing $a$ and $b$ alongside index) should return $\binom{n}{2}$; an input where no pair satisfies it (strictly decreasing $a$ and/or $b$) should return 0. Ties in $a$-value or $b$-value need a consistent tie-breaking rule: because both constraints are strict ($a_i < a_j$, not $\le$), the sweep must never insert a left-half element into the Fenwick tree while its $a$-value is only equal (not strictly less) to the current right-half element's $a$-value, and the Fenwick query must count strictly-less $b$-ranks (not less-or-equal). Get either of these backwards and ties silently turn into double-counted or missed pairs, since a tied element could otherwise be treated as satisfying a strict inequality against itself or against another tied element.

13. Applications & Alternatives

14. Exercises & Mastery

Easy

1. Take a new set of 5 triples of your own choosing and verify, by brute force, the count CDQ divide and conquer would produce — then trace the recursion by hand as in Section 8.

Medium

1. Extend the implementation to count pairs with $a_i < a_j$ but $b_i > b_j$ (a mixed-direction constraint). Think about what changes in the sweep and the Fenwick-tree query — does the tree need to be queried from the other end, or does the $b$-ranking need to be reversed?

Hard

1. Design (conceptually; no implementation required) how you would generalize this technique to a fourth dimension — four constraints that must all hold simultaneously. What additional structure would the cross-half step need, and does "one divide and conquer, one sort, one data structure" still describe it, or does a fourth dimension require nesting a second data structure inside the first?

Review rhythm: tomorrow, reconstruct the recursion structure and the reason index-first splitting is necessary, without notes; next week, re-implement the Fenwick-tree cross-count sweep from memory in a language of your choice; several weeks later, recognize this pattern when a new problem presents multiple sortable constraints, before being told CDQ divide and conquer applies. Finally, teach the "one divide and conquer, one sort, one data structure" framing to someone who already understands merge-sort-based Inversion Count.

15. Summary Cheat Sheet

• CDQ divide and conquer generalizes merge-sort-based Inversion Count to handle one extra constraint dimension per layer.
• Split by index (insertion order) first — this is what makes the $i < j$ constraint automatic for every cross-half pair, with no explicit check.
• Cross-half step: sort both halves by the second dimension and sweep, using a Fenwick tree over the third dimension to count matches in $O(\log n)$ instead of Inversion Count's $O(1)$.
• Recurrence $T(n) = 2T(n/2) + O(n \log n)$ solves to $O(n \log^2 n)$ — one extra $\log n$ factor over plain divide-and-conquer counting.
• Always roll back Fenwick-tree updates made during a cross-half sweep before returning, so sibling recursive calls start clean.
• Strict inequalities need careful tie-breaking: insert only on strictly-smaller comparisons, and query strictly-less ranks, or ties will be double-counted or missed.
• The same "offline, sort, D&C-plus-Fenwick" shape extends to certain DP transitions with two monotonic conditions, using a max/min Fenwick tree instead of a counting one.