xv. Divide and Conquer Optimization

For layered DPs $d{p}_t(j)={\min }_{k<j}(d{p}_{t-1}(k)+C(k,j))$ (“split the array into $t$ segments”), if the optimal $k$ is nondecreasing in $j$, compute one layer in $O(n\log n)$ by divide and conquer over $j$ with shrinking ranges of $k$. Total $O(tn\log n)$. The sufficient condition is the quadrangle inequality on $C$.

Quadrangle inequality (Monge)

$C$ satisfies the quadrangle inequality (QI) if for all $a\le b\le c\le d$:

$C(a,c)+C(b,d)\le C(a,d)+C(b,c).$

Cost $C(k,j)$ of segment $[k,j)$	QI (for minimisation)
range sum (any sign)	equality, both directions
convex function of a nonnegative range sum, e.g. $(\text{sum}{)}^2$	yes
number of equal pairs, number of inversions inside the segment	yes
${\sum }_{i\in [k,j)}|x_i-\text{median}|$ (1D clustering)	yes
concave function of the range sum, number of distinct values, range max	reverse inequality (use them in maximisation)
$p_k{p}_m{p}_j$ (matrix chain)	no

Reverse QI with maximisation is the mirror image and gives the same monotonicity.

Proof: QI implies monotone smallest argmin, and the examples

Let $k=$ smallest optimum for $j$ and $k^{\prime }=$ smallest optimum for $j^{\prime }>j$, and suppose $k^{\prime }<k$. QI with $(a,b,c,d)=(k^{\prime },k,j,j^{\prime })$ gives $C(k^{\prime },j)-C(k,j)\le C(k^{\prime },j^{\prime })-C(k,j^{\prime })$. Optimality of $k^{\prime }$ at $j^{\prime }$ gives $f(k^{\prime })-f(k)\le C(k,j^{\prime })-C(k^{\prime },j^{\prime })$ where $f=d{p}_{t-1}$. Adding, $f(k^{\prime })+C(k^{\prime },j)\le f(k)+C(k,j)$: $k^{\prime }$ is optimal for $j$ too and smaller than $k$, a contradiction.
Examples. With segments $A=[a,b)$, $B=[b,c)$, $D=[c,d)$: for $(\text{sum}{)}^2$ with $x,y,z\ge 0$ the sums, $\text{RHS}-\text{LHS}=(x+y+z{)}^2+y^2-(x+y{)}^2-(y+z{)}^2=2xz\ge 0$. For pair counts, $\text{RHS}-\text{LHS}$ is the number of equal pairs (or inversions) with one element in $A$ and one in $D$, $\ge 0$. For a submodular measure such as the number of distinct values, $f(A\cup B\cup D)+f(B)\le f(A\cup B)+f(B\cup D)$, which is the reverse inequality.

Implementation

vector<ll> prv, cur;
template<class F> void solve(int l, int r, int optl, int optr, F C) {   // fill cur[l..r]
    if (l > r) return;
    int m = (l + r) / 2, opt = optl; ll best = LLONG_MAX;
    for (int k = optl; k <= min(m - 1, optr); k++) {          // k < m: last segment [k, m) nonempty
        if (prv[k] == LLONG_MAX) continue;
        ll v = prv[k] + C(k, m);
        if (v < best) best = v, opt = k;
    }
    cur[m] = best;
    solve(l, m - 1, optl, opt, C); solve(m + 1, r, opt, optr, C);
}
// layers: prv[0] = 0, others INF; for t in 1..T: cur.assign(n + 1, INF); solve(1, n, 0, n - 1, C); swap(prv, cur);

Proof: $O(n\log n)$ per layer

The recursion on $[l,r]$ halves the range of $j$, so it has $O(\log n)$ levels. On one level, the subproblems’ $k$-ranges $[\text{optl},\text{optr}]$ are consecutive and overlap only at endpoints (each split passes $\text{opt}$ to both sides), so the total length scanned on a level is $O(n+\text{number of subproblems})=O(n)$. Hence $O(n\log n)$ per layer, assuming $C$ is $O(1)$.

Costs that are not $O(1)$

If $C(k,j)$ is maintained incrementally (pairs of equal values, distinct counts), keep a Mo-style window and move its ends to $[k,j)$ on each evaluation. Within one layer the window moves $O(n\log n)$ times in total, because along the recursion the evaluations of a subproblem form a contiguous sweep of $k$ and the jumps between subproblems are bounded by the subproblem sizes. CF 868F “Yet Another Minimization Problem” (cost = equal pairs) is the standard example.

int L = 0, R = 0; ll window = 0;                          // window [L, R), cnt[] of values
auto C = [&](int l, int r) {
    while (R < r) window += cnt[a[R++]]++;
    while (L > l) window += cnt[a[--L]]++;
    while (R > r) window -= --cnt[a[--R]];
    while (L < l) window -= --cnt[a[L++]];
    return window;
};

Related tools

Shape	Tool	Cost
layered, Monge, offline	D&C (this note), or SMAWK per layer	$O(tn\log n)$ / $O(tn)$
single layer, online ($d{p}_j$ depends on $d{p}_k$ of the same layer)	binary-search queue / LARSCH (1D1D)	$O(n\log n)$ / $O(n)$
many layers, answer convex in $t$	Aliens trick removes the layer dimension (Aliens)	$O(n\log n\log C)$
interval DP $d{p}_{l,r}$	Knuth–Yao (Knuth)	$O(n^2)$
$d{p}_i={\min }_{j}d{p}_j+b_j{x}_i$ (linear in a per-transition slope/intercept)	convex hull trick (CHT)	$O(n)$ / $O(n\log n)$
fixed-width window, no Monge structure needed at all	monotonic queue (Monotonic Queue)	$O(n)$

Monotonicity of the argmin is also often checkable empirically: run the $O(t{n}^2)$ DP on random small inputs and assert that the smallest argmins are nondecreasing.

D&C optimization vs the Aliens trick, when both apply (“partition into exactly $t$ parts” with a convex cost): D&C keeps the layer dimension and costs $O(tn\log n)$; Aliens removes it entirely, costing $O(n\log n\log C)$ regardless of $t$. When $t$ is large (say $10^5$), Aliens is the only practical option. When $t$ is small, D&C is simpler to implement and needs no convexity assumption on the answer-vs-$t$ curve — only the per-layer quadrangle inequality.