Slope Trick

Maintain an entire convex piecewise-linear function in a pair of heaps, supporting the operations a DP needs in $O(\log n)$ each. It turns a DP whose state is a function into one whose state is a data structure.

The representation

A convex piecewise-linear $f$ is determined by:

• its minimum value $\mathrm{minf}$,
• the multiset of slope-change points to the left of the minimum (kept in a max-heap $L$),
• the multiset of slope-change points to the right (kept in a min-heap $R$).

Each breakpoint appears once per unit of slope change. Convexity guarantees $\max L\le \min R$.

The operations

Operation	Implementation	Cost
$f(x)+=|x-a|$	push $a$ to both heaps, then rebalance; minf += max(0, L.top() - R.top())	$O(\log n)$
$f(x)+=\max (0,x-a)$	push $a$ to $R$ only (with a rebalance)	$O(\log n)$
$f(x)+=\max (0,a-x)$	push $a$ to $L$ only (with a rebalance)	$O(\log n)$
$f(x)+=c$	minf += c	$O(1)$
shift: $f(x)\to f(x-c)$	lazy offsets on both heaps	$O(1)$
prefix min: $g(x)={\min }_{y\le x}f(y)$	clear $R$	$O(1)$
suffix min: $g(x)={\min }_{y\ge x}f(y)$	clear $L$	$O(1)$
sliding min: $g(x)={\min }_{x-b\le y\le x-a}f(y)$	shift $L$ by $a$, shift $R$ by $b$	$O(1)$
query the minimum	minf	$O(1)$
query $f(x)$ at a point	sum the contributions — $O(n)$, rarely needed

Adding $|x-a|$, concretely

priority_queue<long long> L;                                   // max-heap
priority_queue<long long, vector<long long>, greater<>> R;     // min-heap
long long addL = 0, addR = 0, minf = 0;
 
void addAbs(long long a) {
    L.push(a - addL);
    R.push(a - addR);
    long long l = L.top() + addL, r = R.top() + addR;
    if (l > r) {                                               // fix the ordering
        L.pop(); R.pop();
        L.push(r - addL); R.push(l - addR);
        minf += l - r;
    }
}

The minf += l - r line is the only place the minimum value changes, and it is exactly the amount by which the two pushed breakpoints were out of order.

The canonical problem

“Given $a_1..a_n$, make the sequence non-decreasing with the minimum total $\sum |a_i-b_i|$.”

Define $f_i(x)$ = minimum cost for the first $i$ elements with $b_i\le x$. Then

$f_i(x)=({\min }_{y\le x}{f}_{i-1}(y))+|x-a_i|.$

Each step is one “clear $R$” plus one “add $|x-a_i|$”. Total $O(n\log n)$, and the answer is the final minf.

long long minCostNonDecreasing(vector<long long>& a) {
    priority_queue<long long> L;
    long long ans = 0;
    for (long long x : a) {
        L.push(x);
        if (L.top() > x) { ans += L.top() - x; L.pop(); L.push(x); }
    }
    return ans;
}

Eight lines, and it is one of the most striking algorithms in competitive programming — the $R$ heap disappears entirely because the prefix-min clears it every step.

For strictly increasing, subtract $i$ from each $a_i$ first; the problem becomes non-decreasing.

When it applies

Signal
The DP value as a function of one parameter is convex	required
Transitions add $|x-a|$, $\max (0,x-a)$, or constants	✔
Transitions take prefix/suffix minima or shift the function	✔
You only need the final minimum, not the whole function	✔
The function is not convex	✘ — slope trick is invalid

Convexity is preserved by all the operations above, which is why the representation stays valid throughout.

Related techniques

Technique	State is
Slope trick	a convex piecewise-linear function, in heaps
CHT	a set of lines, lower envelope
Li Chao tree	a set of lines, in a segment tree
Aliens trick	a convex sequence indexed by a group count
”Segment tree beats” on a convex function	a function with range updates

All four exploit convexity; slope trick is the one that keeps the entire function around.

See also: Convex Hull Trick · Aliens Trick · Binary Heap