xvii. Monotone Queue, 1D1D and SMAWK

Three tools for $d{p}_i={\min }_j(d{p}_j+w(j,i))$:

• monotone deque when $w(j,i)=f(j)+g(i)$ and $j$ ranges over a window whose ends only move right: $O(n)$;
• binary-search decision queue (“1D1D”) when $w$ satisfies the quadrangle inequality and $dp$ is computed online: $O(n\log n)$;
• SMAWK for row minima of a totally monotone matrix known in advance: $O(n+m)$; LARSCH extends it to the online case in $O(n)$.

Sliding-window minimum

deque<int> dq;                                             // indices j with increasing dp[j] + f(j)
for (int i = 1; i <= n; i++) {
    int j = i - 1; while (sz(dq) && val(dq.back()) >= val(j)) dq.pop_back(); dq.push_back(j);   // val(j) = dp[j] + f(j)
    while (dq.front() < left(i)) dq.pop_front();                                               // left(i) nondecreasing
    dp[i] = val(dq.front()) + g(i);
}

Uses: jumps of length at most $k$, segments of length in $[a,b]$ (push $j=i-a$ when it becomes available), bounded knapsack per residue class (Knapsack), max subarray with length limit. If the window’s left end can move left, use a segment tree.

The window doesn’t have to be a fixed width — only that the valid range of $j$ is contiguous and moves monotonically:

Condition on valid $j$	How the ends move
$i-k\le j<i$	fixed width $k$
$\text{pref}[i]-\text{pref}[j]\le W$	two pointers find the left end
$a_i-a_j\le D$ (sorted $a$)	two pointers
$j\ge \text{lastBad}[i]$, lastBad non-decreasing	two pointers

This same deque is also the standard $O(1)$-amortized minimum queue outside DP entirely (Monotonic Queue), which is what makes Mo’s-algorithm variants with a removable-min aggregate and some graph algorithms fast (Mo’s Algorithm).

Debugging a monotone-queue optimization

Four checks, in order: (1) is the window’s left end monotone non-decreasing — if not, the deque is simply wrong, not slow; (2) popping the front happens before querying, popping the back before pushing; (3) >= vs > in the back-pop comparison only affects deque length, not correctness, so don’t chase a bug there; (4) dp[i] is pushed after it’s computed — pushing before creates a self-dependency.

Proof: the deque holds every candidate that can still win

An index $j$ is removed from the back only when a newer index $j^{\prime }>j$ has $\text{val}(j^{\prime })\le \text{val}(j)$; since windows only move right, $j^{\prime }$ stays in the window at least as long as $j$, so $j$ can never be the unique minimum again. Indices removed from the front are out of the window forever. So the deque’s front is the minimum of the current window, and its values are increasing from front to back. Each index is pushed and popped once: $O(n)$.

1D1D with the quadrangle inequality

If $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ for $a\le b\le c\le d$, then a newer decision $x$, once better than an older decision at some point, stays better for all later points. Keep a stack of segments (first position, decision); a new decision takes over a suffix found by binary search.

template<class T, class W> vector<T> oneD1D(int n, T dp0, W w) {   // dp[x] = min_{i<x} dp[i] + w(i, x)
    vector<T> dp(n + 1); dp[0] = dp0;
    vector<pair<int, int>> seg{{1, 0}};                      // (first x where decision is best, decision)
    auto val = [&](int i, int x) { return dp[i] + w(i, x); };
    for (int x = 1; x <= n; x++) {
        int k = prev(upper_bound(all(seg), pair(x, INT_MAX)))->second;
        dp[x] = val(k, x);
        if (x == n) break;
        while (true) {
            if (seg.empty()) { seg.push_back({x + 1, x}); break; }
            auto [y, old] = seg.back(); int st = max(y, x + 1);
            if (val(x, st) < val(old, st)) { if (y > x) { seg.pop_back(); continue; } seg.push_back({x + 1, x}); break; }
            int lo = st + 1, hi = n + 1;                       // first position where x beats old
            while (lo < hi) { int m = (lo + hi) / 2; if (val(x, m) < val(old, m)) hi = m; else lo = m + 1; }
            if (lo <= n) seg.push_back({lo, x});
            break;
        }
    }
    return dp;
}

Typical costs: $(\text{range sum}-L{)}^2$ or $|\cdot {|}^p$ with $p\ge 1$ (“poetry” / line breaking), $\sqrt{x-i}$ in maximisation. For concave costs in minimisation (reverse QI), a new decision wins a prefix of each older decision’s region instead: process with a deque where new decisions are compared against the front, or use LARSCH-style structures.

Proof: a new decision wins a suffix

Let $i<x$ be two decisions and $x<y<z$ two later positions. QI on $(i,x,y,z)$: $w(i,y)+w(x,z)\le w(i,z)+w(x,y)$, so $(d{p}_x+w(x,z))-(d{p}_i+w(i,z))\le (d{p}_x+w(x,y))-(d{p}_i+w(i,y))$. If $x$ is at least as good as $i$ at $y$, it is at least as good at $z$. So the set of future positions where $x$ beats an older decision is a suffix, and the segment structure (each decision best on a contiguous block, in increasing order of decision) is preserved. Each decision is pushed once and popped at most once; each insertion does one binary search: $O(n\log n)$ evaluations of $w$.

SMAWK

Named for its five authors (Aggarwal, Klawe, Moran, Shor, Wilber). Row minima of an $n\times m$ totally monotone matrix (if a later column beats an earlier one in some row, it also does in every later row; implied by the Monge condition $A_{i,k}+A_{j,l}\le A_{i,l}+A_{j,k}$) in $O(n+m)$ evaluations: reduce the columns to at most $n$ candidates with a stack, recurse on the odd rows, then fill each even row by scanning between its neighbours’ answers.

template<class F> vector<int> smawk(int n, int m, F A) {    // leftmost argmin of every row
    auto rec = [&](auto&& self, const vector<int>& rows, const vector<int>& cols) -> vector<int> {
        if (rows.empty()) return {};
        vector<int> st;
        for (int c : cols) {
            while (sz(st) && A(rows[sz(st) - 1], st.back()) > A(rows[sz(st) - 1], c)) st.pop_back();
            if (sz(st) < sz(rows)) st.push_back(c);
        }
        vector<int> odd; for (int i = 1; i < sz(rows); i += 2) odd.push_back(rows[i]);
        vector<int> so = self(self, odd, st), res(sz(rows));
        for (int i = 1; i < sz(rows); i += 2) res[i] = so[i / 2];
        for (int i = 0, k = 0; i < sz(rows); i += 2) {
            int hi = i + 1 < sz(rows) ? res[i + 1] : st.back();
            res[i] = st[k];
            while (st[k] != hi) { k++; if (A(rows[i], st[k]) < A(rows[i], res[i])) res[i] = st[k]; }
        }
        return res;
    };
    vector<int> r(n), c(m); iota(all(r), 0); iota(all(c), 0);
    return rec(rec, r, c);
}

Proof sketch: REDUCE and the $O(n+m)$ bound

REDUCE keeps the invariant that the $t$-th stack column could still be the minimum of some row with index $\ge t$. Comparing the top column $s$ (position $t$) with a new column $c$ at row $t$: if $c$ is strictly better there, total monotonicity makes $c$ at least as good in all rows $\ge t$, and $s$ can’t be the leftmost minimum of rows $<t$ either (those are covered by earlier stack columns), so $s$ is discarded. Otherwise $c$ can’t win rows $\le t$ and is pushed at position $t+1$ if there is a row left for it. Each column is pushed and popped once: $O(m)$. After REDUCE at most $n$ columns remain. The even rows’ answers lie between the answers of their odd neighbours (monotone argmins), and the fill scan walks the stack once: $O(n)$. So $T(n,m)=O(n+m)+T(n/2,n)$, which sums to $O(n+m)$.

Online case (row $i$‘s entries depend on $dp$ values computed from earlier rows): LARSCH achieves $O(n)$ but is intricate. Simpler: CDQ over the index — compute the left half recursively, then the left half’s decisions are all known, so their contribution to the right half is an offline row-minima problem (SMAWK or the D&C of D&C Optimization), then recurse on the right half: $O(n\log n)$ or $O(n{\log }^{2}n)$.

SMAWK’s real-world reach: Knuth–Plass line/paragraph breaking (least-weight subsequence with a concave cost), all-pairs shortest paths restricted to Monge graphs, RNA secondary-structure prediction, largest empty rectangle, and optimal BSTs whose cost happens to be Monge.

Which one

Shape	Use
$w(j,i)=f(j)+g(i)$, window bounds monotone	deque, $O(n)$
$w(j,i)=a_j{b}_i+\dots$	convex hull trick (CHT)
$w$ Monge (QI), online	1D1D binary search, $O(n\log n)$
$w$ Monge, layered	D&C optimisation or SMAWK per layer
$w$ Monge, all row minima known in advance	SMAWK, $O(n+m)$
min-plus convolution with a convex sequence	SMAWK / D&C (Knapsack)