xix. Slope Trick

When the DP state is a convex piecewise-linear function $f(x)$ with integer breakpoints, store it as its minimum value plus two heaps of breakpoints: $L$ (max-heap, breakpoints left of the minimum, each one = slope changes by 1) and $R$ (min-heap, right of the minimum). Adding $|x-a|$, $\max (0,x-a)$, constants, taking prefix/suffix minima, shifting and sliding-window minima are all $O(\log n)$ or $O(1)$.

struct SlopeTrick {
    ll minf = 0, addL = 0, addR = 0;                       // lazy shifts of the two heaps
    priority_queue<ll> L; priority_queue<ll, vector<ll>, greater<>> R;
    ll topL() const { return L.empty() ? LLONG_MIN / 4 : L.top() + addL; }
    ll topR() const { return R.empty() ? LLONG_MAX / 4 : R.top() + addR; }
    void pushL(ll a) { L.push(a - addL); }
    void pushR(ll a) { R.push(a - addR); }
    ll popL() { ll v = topL(); L.pop(); return v; }
    ll popR() { ll v = topR(); R.pop(); return v; }
    void addXMinusA(ll a) { minf += max(0LL, topL() - a); pushL(a); pushR(popL()); }   // f += max(0, x - a)
    void addAMinusX(ll a) { minf += max(0LL, a - topR()); pushR(a); pushL(popR()); }   // f += max(0, a - x)
    void addAbs(ll a) { addXMinusA(a); addAMinusX(a); }                                  // f += |x - a|
    void prefixMin() { R = {}; }                            // f(x) <- min_{y <= x} f(y)
    void suffixMin() { L = {}; }                            // f(x) <- min_{y >= x} f(y)
    void slideMin(ll a, ll b) { addL += a; addR += b; }     // f(x) <- min_{x-b <= y <= x-a} f(y), a <= b
    void shift(ll a) { addL += a; addR += a; }              // f(x) <- f(x - a)
};

The minimum is attained on $[\text{topL},\text{topR}]$. Evaluating $f$ at a point costs $O(n)$ (sum the hinge functions), so recover a minimiser from the heaps instead.

Proof: the representation and the update rules

A convex piecewise-linear function with integer slopes is determined by its minimum value and its breakpoints with multiplicity: going right from the flat part, the slope increases by 1 at each element of $R$; going left, it decreases by 1 at each element of $L$; convexity is exactly $\max L\le \min R$.
Adding $\max (0,x-a)$ raises the slope by 1 at $a$. If $a\ge \max L$, the minimum segment’s left end is unaffected and $a$ simply joins $R$ (the code pushes $a$ to $L$ and then moves the maximum of $L$, which is $a$, to $R$). If $a<l=\max L$, the old flat part $[l,r]$ now has slope $+1$ to the right of $a$, so the new flat part is $[\max (a,l^{\prime }),l]$ where $l^{\prime }$ is the next element of $L$; the minimum increases by $l-a$ (the hinge’s value at $l$), and $l$ moves from $L$ to $R$ while $a$ joins $L$, which is exactly “push $a$ to $L$, move $\max L$ to $R$”. The other hinge is symmetric, and $|x-a|$ is the sum of both.
Prefix minimum makes every slope to the right of the minimum 0: drop $R$. Sliding minimum ${\min }_{y\in [x-b,x-a]}f(y)$ translates the decreasing part right by $a$ and the increasing part right by $b$ (the flat part widens by $b-a$), which is the pair of lazy shifts.

Classic problems

Make the sequence non-decreasing with minimum $\sum |a_i-b_i|$: $f_i(x)={\min }_{y\le x}{f}_{i-1}(y)+|x-a_i|$. Only $L$ survives the prefix minima:

ll minCostNonDecreasing(const vector<ll>& a) {             // strictly increasing: use a_i - i
    priority_queue<ll> L; ll ans = 0;
    for (ll x : a) { L.push(x); if (L.top() > x) { ans += L.top() - x; L.pop(); L.push(x); } }
    return ans;
}

Problem	Transition
$\min\sum	a_i - b_i
same with $	b_i - b_{i-1}
$b_i-b_{i-1}\in [lo,hi]$	sliding min with $[lo,hi]$
cost $c_i\cdot	x - a_i
buy/sell one unit per day for max profit	the heap greedy is the slope trick of the profit function
tree version: edges’ lengths adjustable at cost $	\Delta

Merging functions: the sum of two convex functions has the union of breakpoints; with only $L$ heaps (after prefix minima) merging is heap merging, $O(n{\log }^{2}n)$ with small-to-large or $O(n\log n)$ with leftist/pairing heaps (Heaps).

Related

• The answer as a function of “number of groups” being convex is the Aliens trick (Aliens); here the function is of a value.
• Non-integer breakpoints are fine as long as comparisons are exact.
• When the function is convex but not piecewise linear with few pieces, keep it in a balanced BST or segment tree over the domain (sum of convex functions, min-plus convolution of convex functions = merge of slope sequences).

Recognising when it applies: the DP value as a function of one parameter must be convex, with transitions limited to adding $|x-a|$/$\max (0,x-a)$/constants, taking prefix/suffix minima, or shifting — and you only ever need the final minimum, never to query $f$ at an arbitrary point cheaply. If the function isn’t convex, slope trick is simply invalid, not slow.

Several techniques exploit convexity by keeping a different representation of the same kind of object: slope trick keeps the whole convex function in two heaps; CHT and Li Chao tree keep a set of lines (a lower/upper envelope) instead of a function of one variable per DP state; the Aliens trick keeps only one point of a convex sequence indexed by group count, found by binary search rather than maintained directly.