This tutorial is nominated for the blog posts competition from cadmiumky. Thanks to him for this initiative!
Also thanks to Ghos007, dima210121012101, dmitryAdams and ChatGPT for proofreading this post and giving useful feedback.
CDQ Divide & Conquer is an interesting algorithmic technique that nobody talks about (at least in Russian CP community). However, it is quite powerful, as it often provides unexpectedly clean solutions to seemingly tedious problems. In this tutorial, I will discuss different contexts where this method is useful. I also want to collect what I have seen about this technique on the Internet in one place and add my own insights. Credit to robert1003's blog where I first learned this method.
The main idea of this technique is to calculate the influence/contribution of one half to the other while dividing. Let’s see how this can be useful.
3D Queries
Problem. You are given $$$n$$$ points $$$(x_i, y_i, z_i)$$$ and $$$q$$$ queries $$$(a_i, b_i, c_i)$$$. For each query $$$i$$$, you need to count the number of points $$$j$$$ such that $$$x_j \lt a_i$$$, $$$y_j \lt b_i$$$ and $$$z_j \lt c_i$$$.
The 2D version of this problem is well known and can be solved using sweepline with Fenwick tree, but the 3D case seems tedious. With CDQ, however, it becomes much simpler.
As in a typical sweepline problem, define events $$$(x, y, z, \text{type})$$$, where $$$\text{type} = 1$$$ means "add a point $$$(x, y, z)$$$", $$$\text{type} = 2$$$ means "count the number of points with all coordinates smaller than $$$(x, y, z)$$$". Sort the events by $$$x$$$. If two events have the same $$$x$$$ value, sort them by type in descending order so that type 2 comes before type 1. This is needed to ensure that points with $$$x_j = a_i$$$ are not counted.
Then write a function $$$\text{solve3d}(l, r)$$$ that solves the problem as if only the events in the interval $$$[l, r)$$$ existed. The idea is simple:
- If $$$r - l = 1$$$, return.
- Solve the problem recursively for the left half: $$$\text{solve3d}(l, \text{mid})$$$
- Compute the contribution of the left part to the right — that is, how update queries from the left affect calculation queries from the right. Details of this computation are explained below.
- Solve the problem recursively for the right half: $$$\text{solve3d}(\text{mid}, r)$$$
The nice thing about partitioning into halves is that, for each "add point" $$$(x_i, y_i, z_i)$$$ event from the left part, we have $$$x_i \lt a_j$$$ for every "calculate" event $$$(a_j, b_j, c_j)$$$ in the right part because of the sorting. So for one dimension, the inequality holds automatically. The problem now reduces to this:
Problem (reduced). You are given $$$n$$$ points $$$(y_i, z_i)$$$ from the left half and $$$q$$$ queries $$$(b_i, c_i)$$$ from the right half. For each query $$$i$$$, count the number of points $$$j$$$ such that $$$y_j \lt b_i$$$ and $$$z_j \lt c_i$$$.
This is the standard 2D problem (for convenience, assume it's implemented in a $$$\text{solve2d}$$$ function). Once we computed the full contribution of the left half, we treat the halves as independent. The time complexity is $$$\mathcal{O}(n \log^2 n)$$$, since we perform an $$$\mathcal{O}(n \log n)$$$ sweepline on each of $$$\log n$$$ layers of D&C.
You can see the implementation of this algorithm in the next section.
Note that the algorithm above does not rely on the fact that each point contributes exactly $$$1$$$ to the answer. It would still work if points had arbitrary weights. Also you can query sums on arbitrary 3D ranges by doing inclusion-exclusion like in prefix sums.
Tasks for practice
ROI Regional Stage 2026 Sliding Windows
Arbitrary-dimensional queries
The recursive algorithm above just drops one dimension. To handle a fourth dimension, for example, you only need to write a $$$\text{solve4d()}$$$ function that calls $$$\text{solve3d()}$$$ to compute the contribution.
This method generalizes to any number of dimensions, giving a time complexity of $$$\mathcal{O}(n \log^{d - 1} n)$$$ for $$$d$$$ dimensions.
Tasks for practice
You can try to apply 4D CDQ in IZhO 2020 Nasty Donchick, good luck :)
I didn't manage to fit 40 4-dimensional CDQs in the limit though even with heavy constant factor optimizations.
Generalization for min/max
By the way, this method works not only for sums but also for min/max. The only limitation is that you can compute min/max only over prefix ranges, not over general ones directly, because the operation is not invertible. There is a workaround though: just add more dimensions!
For example, suppose we want the minimum on $$$[x_l, x_r] \times [y_l, y_r] \times [z_l, z_r]$$$. Then we want points $$$(x, y, z)$$$ that satisfy $$$x_l \le x \le x_r$$$ and $$$y_l \le y \le y_r$$$ and $$$z_l \le z \le z_r$$$.
For the $$$z$$$-dimension, there's no such problem — we can update any segment in segment tree not just prefixes. For $$$x$$$ and $$$y$$$, however, we need to "double" them. That is, consider a 5D point $$$p = (x, x, y, y, z)$$$ and require $$$p_1 \ge x_l$$$, $$$p_2 \le x_r$$$, $$$p_3 \ge y_l$$$, $$$p_4 \le y_r$$$ and $$$z_l \le p_5 \le z_r$$$. Suffix queries can be handled similarly to prefix queries, for example, by multiplying the relevant coordinates by $$$-1$$$. The time complexity is $$$\mathcal{O}(n \log^4 n)$$$ because of 5-dimensional CDQ 💀
MEX on segment with modifications (offline)
Problem. You are given an array $$$a$$$ of $$$n$$$ integers. Also there are $$$q$$$ queries:
- Type 1. Set $$$a_i := x$$$.
- Type 2. Find $$$\text{MEX}(a_l, a_{l + 1}, \cdots, a_{r - 1}, a_r)$$$.
The idea is to maintain intervals where each value $$$x$$$ is excluded.
Formally, let the positions of $$$x$$$ be $$$p_1, p_2, \cdots, p_k$$$. Then, for each $$$i$$$, we create an interval $$$(p_i, p_{i + 1})$$$ with weight $$$x$$$. For convenience, we also add $$$(-1, p_1)$$$ and $$$(p_k, n)$$$. If $$$x$$$ does not appear in the array at all, we add a single interval $$$(-1, n)$$$. Now a query of type 2 can be answered by taking the minimum weight of all intervals fully covering $$$[l, r]$$$. Intuitively, if some occurrence of $$$x$$$ was before the left border $$$l$$$, and the next occurrence is after $$$r$$$, this means that $$$x$$$ does not appear in this segment.
Without modifications, this reduces the problem to "minimum in prefix subrectangle" queries: treat intervals as points and queries as subrectangles. The time complexity is $$$\mathcal{O}(n \log n)$$$.
To handle modifications, we need to update the set of intervals after each change. To do this, we store positions of each value $$$x$$$ in a std::vector of std::set’s. When processing a modification at position $$$i$$$, we remove $$$i$$$ from the set corresponding to the old value of $$$a_i$$$. Before the removal, $$$i$$$ splits one existing interval into two, so we delete the two intervals that had $$$i$$$ as an endpoint and add the merged interval formed by its neighbors. Then we set $$$a_i := x$$$ and insert $$$i$$$ into the set for the new value. This insertion splits one existing interval into two, so we delete the merged interval and add the two new intervals created by inserting $$$i$$$.
The main difficulty is that now the set of intervals is dynamic, i.e., intervals may be added or removed as the algorithm runs. The idea is to maintain the "time of life" of each object. That is, each interval is now described by four integers: $$$(l, r, T_l, T_r)$$$. This means that the interval was added at query with index $$$T_l$$$ (or $$$-1$$$ if it existed from the beginning) and was removed in query with index $$$T_r$$$ (or $$$q$$$ if it was never removed). Note that we describe a query by a triple $$$(l, r, T)$$$ now. The problem reduces to the following:
Problem (reduced). You are given $$$n$$$ points $$$(l_i, r_i)$$$ with weights $$$w_i$$$. Each point $$$i$$$ appears at time $$$lt_i$$$ and disappears at time $$$rt_i$$$. Also there are $$$q$$$ queries $$$(lq_i, rq_i)$$$. For each query, find the minimum weight of all points $$$j$$$ such that:
$$$l_j \lt lq_i$$$
$$$r_j \gt rq_i$$$
$$$j$$$ is "alive" at time $$$i$$$. Formally, $$$lt_j \le i \le rt_j$$$
At first glance, this looks like a four-dimensional problem, since each point is described by four parameters (and weight). However, there is a way to avoid this.
Run CDQ on events sorted by $$$l_i$$$ / $$$lq_i$$$. When computing the contributions, the inequality on left borders is satisfied automatically, so we can drop this dimension. Then run a sweepline over time. For each point, create two events: an add event at time $$$lt_i$$$ and a remove event at time $$$rt_i$$$. Also create one event for each query. When processing an add event for point $$$i$$$, insert weight $$$w_i$$$ at position $$$r_i$$$ in a segment tree. When processing a remove event, replace this value with $$$+\infty$$$. For each query $$$i$$$, query the minimum on the suffix $$$(rq_i, +\infty)$$$ of the segment tree.
For correctness, right borders must be unique. Otherwise, removing one point could incorrectly delete another point with the same $$$r$$$. This is easy to fix by compressing $$$r_i$$$ values and assigning unique indices (by sorting and using their order). The time complexity is $$$\mathcal{O}(n \log^2 n)$$$ because of three-dimensional queries.
Tasks for practice
Long tour of Moscow Open Olympiad 2018-2019, problem "Dima and Array"
Online FFT
Problem. You are given arrays $$$a$$$, $$$b$$$ and $$$r$$$, all of length $$$n$$$. You need to calculate a recurrent array $$$dp_k = a_k \cdot \sum_{i + j = k}{(dp_i \cdot r_j)} + b_k$$$ also of length $$$n$$$.
The problem is that this recurrence depends on its previous terms so we can't solve it by just multiplying polynomials. Once again, we can apply CDQ on this DP.
Suppose we are computing the contribution of DP's in the range $$$[L, M)$$$ to the range $$$[M, R)$$$ (and we have already computed the DP values in the range $$$[L; M)$$$). For now, let's ignore $$$a_k$$$'s and $$$b_k$$$'s for a moment — we will apply the transform $$$dp_k := a_k \cdot dp_k + b_k$$$ inside the $$$\text{solve}(k, k + 1)$$$ call later. At this stage, we treat unprocessed $$$dp_k$$$ as $$$\sum_{i + j = k}{dp_i \cdot r_j}$$$. For our current ranges $$$[L; M)$$$ and $$$[M; R)$$$, what values of $$$i$$$ and $$$j$$$ are actually relevant for computing the influence? Exactly those that form cross contributions: $$$i \in [L; M)$$$ and $$$j \in [0; R - L)$$$. The second bound holds because the smallest contributing index is $$$i = L$$$ and the largest receiving index is $$$k = R - 1$$$, so the maximum possible difference is $$$(R - 1) - L \lt R - L$$$.
We can then use FFT to multiply $$$DP[L:M]$$$ with $$$r[0:R - L]$$$ (here ":" denotes slice as in Python). Then add the results of multiplications to the DP's from the right half. The time complexity is $$$\mathcal{O}(n \log^2 n)$$$ because we convolve arrays of total size $$$\mathcal{O}(n)$$$ in $$$\mathcal{O}(n \log n)$$$ time on each of $$$\mathcal{O(\log n)}$$$ recursion layers.
Tasks for practice
CDQ + SOS DP
This is similar to the previous section. Let's look at the following DP:
Problem. You are given arrays $$$a$$$, $$$b$$$ and $$$r$$$, all of length $$$2^n$$$. You need to calculate recurrence $$$dp_i = a_i \cdot \sum_{j \subset i}{dp_j} + b_j$$$. That is, for each mask we take the sum of DPs of all submasks, multiply by given constant and add another constant.
The idea is simple: run CDQ D&C on masks. Again, we want to compute the influence of $$$[L; M)$$$ on $$$[M; R)$$$. The binary representations of numbers in the first half look like [LCP]0[anything] and in the second half [LCP]1[anything]. Here, LCP means longest common prefix. Let its length be $$$k$$$. When computing the influence, note that the submask condition automatically holds for the first $$$k + 1$$$ bits. On the remaining bits, it becomes a standard SOS DP on an array of size $$$2^{n - k - 1}$$$.
So the method is: recursively compute the left half, run SOS DP to propagate its contribution, then recursively compute the right half. At a leaf, apply $$$dp_i := a_i \cdot dp_i + b_i$$$. The time complexity is $$$\mathcal{O}(2^n \cdot n^2)$$$, because we do $$$O(2^n)$$$ work per level and there are $$$\log_2(2^n) = n$$$ levels.
Tasks for practice
USACO 2023 Feb Platinum, Problem Setting.
CDQ on Graph Trick
The following 1D problem is well known. I assume you already know how to solve it:
Problem (1D). You are given a directed graph on $$$n$$$ vertices. Initially, there are $$$m$$$ edges $$$(u_i, v_i)$$$. Then you need to process queries. Each query gives three integers $$$v$$$, $$$l$$$ and $$$r$$$ and asks you to add edges $$$(v, l), (v, l + 1), \cdots, (v, r - 1), (v, r)$$$. After all queries, find the shortest path between $$$s$$$ and $$$t$$$.
This can be solved in $$$\mathcal{O}(n \log n)$$$ using segment tree on graph trick. But there is an even harder problem that is still solvable using this trick:
Problem (2D). You are given a directed graph on $$$n$$$ vertices and an array $$$a$$$. Initially there are $$$m$$$ edges $$$(u_i, v_i)$$$. Then you need to process queries. Each query gives four integers $$$v$$$, $$$l$$$, $$$r$$$ and $$$x$$$ and asks you to add edges $$$(v, i)$$$ for each $$$i$$$ such that $$$l \le i \le r$$$ and $$$a_i \lt x$$$. After all queries, find the shortest path between $$$s$$$ and $$$t$$$.
Let's use persistent segment tree on graph trick to solve this problem. The idea is to do a sweepline where we sort by $$$a_i$$$ / $$$x$$$. We can treat $$$a_i$$$ as the "time" when $$$i$$$-th element appears (activates). Then, there are two types of events:
- Activate $$$i$$$-th position
- Add an edge from given node $$$v$$$ to all already activated nodes in range $$$[l; r]$$$
Initially there are no virtual nodes (as in implicit segment tree). For the queries of the first type, add the path from the root to $$$i$$$ in the segment tree. If some node from this path already exists, add a link from the new version to the old one. For the queries of the second type, as in the 1D problem, add edges from $$$v$$$ to the latest versions of nodes of segment tree that form range $$$[l; r]$$$. The copying of versions is needed to ensure that we don't break old second type queries by adding a new position that was not activated at that moment. The time complexity is $$$\mathcal{O}(n \log n)$$$.
Moreover, we can solve even the 3D version:
Problem (3D). You are given a directed graph on $$$n$$$ vertices and arrays $$$a$$$ and $$$b$$$. Initially there are $$$m$$$ edges $$$(u_i, v_i)$$$. Then you need to process queries. Each query gives you five integers $$$v$$$, $$$l$$$, $$$r$$$, $$$x$$$, $$$y$$$, and and asks you to add edges $$$(v, i)$$$ for each $$$i$$$ such that $$$l \le i \le r$$$, $$$a_i \lt x$$$ and $$$b_i \lt y$$$. After all queries, find the shortest path between $$$s$$$ and $$$t$$$.
The solution is to do CDQ on $$$b_i$$$, build a persistent segment tree on the nodes from the left half and use the 2D solution with queries from the right half (that have greater $$$y$$$'s than $$$b_i$$$'s from the left). The time complexity is $$$\mathcal{O}(n \log^2 n)$$$.
Of course, this algorithm generalizes to arbitrary number of dimensions $$$d$$$ by using $$$(d - 1)$$$-dimensional CDQ inside of $$$d$$$-dimensional CDQ.
Tasks for practice
I am not aware of any problems in which you can use the 3D algorithm. Here are some problems where you can use the 2D method:
