βš™οΈAlgorithmAdvanced

Slope Trick

Key Points

  • β€’
    Slope Trick is a technique to maintain a convex piecewise-linear function implicitly using two heaps and a running constant.
  • β€’
    It supports adding V-shaped costs like |x βˆ’ a|, shifting the function horizontally, and taking prefix or suffix minima in O(log n) per update.
  • β€’
    The function is represented as a base value plus sums of hinge functions, with breakpoints stored in a max-heap (left) and a min-heap (right).
  • β€’
    The minimum value is tracked explicitly, and the minimizer lies between the tops of the two heaps.
  • β€’
    A classic application is the O(n log n) solution to make a sequence non-decreasing with minimum L1 cost.
  • β€’
    Operations map to DP recurrences such as (x) = + min_{y ≀ x} (y).
  • β€’
    Shifting the argument βˆ’ c) is O(1) by lazily offsetting heap elements.
  • β€’
    The method is elegant but specialized; it shines for convex DP transitions with hinge-like updates and min-closures.

Prerequisites

  • β†’Convexity and piecewise-linear functions β€” Understanding why sums of hinge functions are convex and how slopes change at breakpoints is essential.
  • β†’Priority queues (heaps) β€” The implementation relies on max- and min-heaps to store breakpoints and perform O(log n) updates.
  • β†’Dynamic programming basics β€” You should recognize state transitions and how slope-trick updates encode DP recurrences.
  • β†’Big-O notation β€” To reason about time/space complexity of the updates and overall algorithm.
  • β†’Absolute deviation and medians β€” Intuition for why |x βˆ’ a| sums are minimized at medians helps interpret heap behavior.

Detailed Explanation

Tap terms for definitions

01Overview

Slope Trick is a data-structural view of convex, piecewise-linear functions that lets us model and update dynamic programming states efficiently. Instead of storing a function as a huge array or recomputing its values, we keep only where its slope changes (the breakpoints). The function is implicitly represented as a constant base plus a sum of hinge functions like max(0, a βˆ’ x) and max(0, x βˆ’ b). Practically, we store two sets of breakpoints in two heaps: a max-heap for the left hinges and a min-heap for the right hinges. Common operationsβ€”adding an absolute value term |x βˆ’ a|, taking a prefix minimum g(x) = min_{y ≀ x} f(y), or shifting the argument f(x) β†’ f(x βˆ’ c)β€”translate to simple heap operations and lazy offsets.

Why does this matter? Many DP problems on sequences reduce to maintaining the cost as a convex function over the last choice x. For example, in making a sequence non-decreasing with minimum absolute adjustment, the transition is f_i(x) = |x βˆ’ a_i| + min_{y ≀ x} f_{iβˆ’1}(y). Naively evaluating min over all y is quadratic; with Slope Trick we compress f_{iβˆ’1} into heaps and do each step in O(log n). The running minimum value is tracked explicitly, so querying the current optimal value is O(1), and the optimal x lies within an easily derived interval from heap tops.

02Intuition & Analogies

Imagine you are tracking the price of adjusting a knob to a position x. Every time you add a V-shaped cost |x βˆ’ a|, you are saying, β€œit's cheapest near a, and it gets linearly worse as I move away.” If you add many such V's, the total cost is still a mountain range made of straight segmentsβ€”a piecewise-linear convex curve. The only interesting parts are where the slope changesβ€”like ridges on the mountain. Slope Trick stores just those ridges instead of the whole mountain.

Think of two teams of hikers holding a rope at height equal to the current minimum cost. The left team holds pegs at positions where cost increases if you move left (left hinges), and the right team holds pegs where cost increases if you move right (right hinges). Adding |x βˆ’ a| is like letting both teams add a peg at a, but one peg may be reassigned between teams depending on balance, and the rope length (the base cost) increases by exactly the amount needed to keep both sides properly tensioned. Taking a prefix minimum min_{y ≀ x} is like saying β€œif going to the right ever increases cost, don't climbβ€”just stay at the cheapest from the past”; the right team's pegs no longer matter, so you drop them. Shifting f(x) to f(x βˆ’ c) is sliding the entire mountain c units to the right; you don't move each peg individually, you simply remember a global shift.

This mental model helps: heaps store pegs, base holds the current minimal height, and offsets remember how much we've slid the mountain. Every operation just tweaks pegs, base, or offsets, never reconstructing the full terrain.

03Formal Definition

We maintain a convex piecewise-linear function f: \{+\} in the canonical form \[ f(x) = C \, + \, (0, \, l - x) \, + \, (0, \, x - r), \] where C is a scalar (the current minimum value), L is a multiset of left breakpoints, and R is a multiset of right breakpoints. Convexity holds because sums of convex hinge functions are convex. The minimizer set is the interval [ L, R] (interpreting empty as ). We store L as a max-heap and R as a min-heap with lazy offsets addL, addR so that shifting arguments is O(1). Supported operations include: (1) ad_minu(a): add g(x) = (0, x - a), which inserts a into R, and possibly moves an element from L to R while increasing C by the required adjustment; (2) ad_minu(a): add g(x) = (0, a - x), which symmetrically inserts a into L, possibly moving from R to L and adjusting C; (3) ad(a): add by composing the previous two; (4) shif(c): replace f by x f(x - c) by setting addL addL + c and addR addR + c; (5) chmi: replace f by x f(y) by discarding R; (6) chmi similarly by discarding L. The minimum value is always C and can be queried in O(1). Each hinge insertion or movement costs O(1) heap operations, hence O( n) time per update.

04When to Use

Use Slope Trick when your DP state is a convex piecewise-linear function of a real/integer parameter, and each transition adds hinge-like costs or takes prefix/suffix minimums or shifts. Common settings:

  • Monotone sequence editing with L1 costs: make a sequence non-decreasing or non-increasing with minimum sum of absolute changes. The recurrence is f_i(x) = |x βˆ’ a_i| + min_{y \le x} f_{iβˆ’1}(y) (or min_{y \ge x}).
  • Convex DP with ramp penalties: costs of the form \max(0, x βˆ’ a) or \max(0, a βˆ’ x), often modeling penalties for exceeding bounds or targets.
  • Problems that need repeated arg shifts: constraints like b_i \ge b_{iβˆ’1} + c are handled by shift_arg(c) followed by prefix-min, i.e., f_i(x) = |x βˆ’ a_i| + min_{y \le x - c} f_{iβˆ’1}(y).
  • Maintaining medians/quantiles under absolute deviation: sums of |x βˆ’ a_i| are represented exactly, with the minimizer being any median of the inserted points.
  • Competitive programming DP optimizations where naive transitions are O(n) per step but become O(\log n) with slope-trick operations. Avoid it if the function is not convex, if transitions are non-piecewise-linear, or when integer constraints are non-convex (e.g., parity-only constraints). In such cases, convex hull trick or other specialized techniques may be more appropriate.

⚠️Common Mistakes

β€’ Confusing function addition with min-convolution: adding |x βˆ’ a| means pointwise addition f(x) ← f(x) + |x βˆ’ a|, not f ← f β‹„ |Β· βˆ’ a|. Slope Trick supports specific min-closure operations (prefix/suffix) and simple shifts; full min-convolution with arbitrary kernels is not directly supported. β€’ Forgetting lazy offsets when reading/writing heap tops: if you store raw keys with addL/addR, always convert via top + offset. Pushing without compensating the offset corrupts breakpoints. β€’ Breaking convexity by mixing non-convex updates: the representation assumes convexity. Adding a concave piece or arbitrary chmin/chmax can invalidate invariants. β€’ Discarding the wrong heap for minima closures: min_{y ≀ x} f(y) drops the right hinges (R), while min_{y β‰₯ x} drops the left hinges (L). Mixing them flips monotonic constraints. β€’ Rebalancing manually: you do not need to enforce L.max ≀ R.min explicitly if you implement add_x_minus_a and add_a_minus_x exactly; these operations move one element across and adjust the base C to maintain the invariant. β€’ Using 32-bit integers for costs: sums of absolute deviations can overflow int. Use 64-bit (long long) for values, offsets, and the base C. β€’ Evaluating f(x) pointwise for large inputs: the power of Slope Trick is avoiding pointwise evaluation. Query the minimum value directly and reconstruct only if necessary.

Key Formulas

Slope Trick Canonical Form

Explanation: Any convex piecewise-linear function maintained by slope trick is represented by a base constant plus left and right hinge sums. L and R are the multisets of slope-change points stored in heaps.

Minimizer Interval

Explanation: For the canonical form, the set of minimizers is any x between the largest left breakpoint and the smallest right breakpoint. If the interval collapses, the minimizer is unique.

Monotone DP Recurrence

Explanation: This models the minimum L1 cost to make a sequence non-decreasing by choosing . The prefix minimum enforces .

Argument Shift

Explanation: Shifting the argument by c translates the graph to the right by c. In the canonical form, it increases all breakpoints by c.

Time Complexity per n updates

Explanation: Each add of a hinge takes a constant number of heap operations, which are O(log n), and prefix/suffix minima and shifts are O(1), leading to O(n log n) over n updates.

Absolute-Deviation Sum

Explanation: This is the prototypical convex piecewise-linear function; its minimizer is any median of the . Slope Trick maintains this exactly via heaps.

Complexity Analysis

Let m be the number of updates (hinge insertions). Each update ad_minu or ad_minu performs at most one heap push and at most one heap pop on each side, plus constant-time arithmetic. Since heap operations take O(log k) when there are k elements, and the number of stored breakpoints grows by at most one per add, the amortized time per update is O(log m). Adding is two such updates, so still O(log m). Shifting the argument by a constant is O(1) via lazy offsets (no heap operations). Taking prefix or suffix minima is O(1) by clearing the corresponding heap; this discards future positive-slope (or negative-slope) contributions and does not touch the other heap. Space usage is O(m) because each contributes at most one new breakpoint to each side across time (constant amortized growth). The base value C and lazy offsets addL/addR are O(1) scalars. Querying the current minimum value is O(1); retrieving the minimizer interval [max L, min R] is O(1) via heap tops (plus offsets). Therefore, a DP over n elements with one prefix-min closure and one addition per step runs in O(n log n) time and O(n) memory. This matches the optimal known bounds for many monotone L1-edit problems and is competitive in practice, due to small constants and cache-friendly priority queues.

Code Examples

Slope Trick Library: add |xβˆ’a|, shifts, and prefix/suffix minima
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SlopeTrick {
5    // Represents a convex piecewise-linear function f in the canonical form:
6    // f(x) = min_f + sum_{l in L} max(0, l - x) + sum_{r in R} max(0, x - r)
7    // L is a max-heap, R is a min-heap. We store keys lazily with offsets addL/addR.
8
9    static constexpr long long INF = (1LL<<60);
10
11    long long min_f;   // current minimum value of f(x)
12    long long addL;    // lazy offset for all keys in L
13    long long addR;    // lazy offset for all keys in R
14
15    priority_queue<long long> L; // stores (l - addL)
16    priority_queue<long long, vector<long long>, greater<long long>> R; // stores (r - addR)
17
18    SlopeTrick(): min_f(0), addL(0), addR(0) {}
19
20    // Helpers to get/push with offsets applied.
21    inline long long topL() const { return L.empty() ? -INF : L.top() + addL; }
22    inline long long topR() const { return R.empty() ?  INF : R.top() + addR; }
23    inline void pushL(long long x) { L.push(x - addL); }
24    inline void pushR(long long x) { R.push(x - addR); }
25
26    // Add g(x) = max(0, a - x)
27    void add_a_minus_x(long long a) {
28        // Prefer to put a into L. If a is larger than the smallest right breakpoint,
29        // move that right breakpoint into L and increase min_f accordingly.
30        if (!R.empty() && a > topR()) {
31            min_f += a - topR();
32            long long t = topR(); R.pop();
33            pushL(t); // moved breakpoint from R to L
34            pushR(a); // insert a into R
35        } else {
36            pushL(a);
37        }
38    }
39
40    // Add g(x) = max(0, x - a)
41    void add_x_minus_a(long long a) {
42        // Symmetric to add_a_minus_x.
43        if (!L.empty() && a < topL()) {
44            min_f += topL() - a;
45            long long t = topL(); L.pop();
46            pushR(t); // moved breakpoint from L to R
47            pushL(a); // insert a into L
48        } else {
49            pushR(a);
50        }
51    }
52
53    // Add |x - a| = max(0, a - x) + max(0, x - a)
54    void add_abs(long long a) {
55        add_a_minus_x(a);
56        add_x_minus_a(a);
57    }
58
59    // Shift argument: g(x) = f(x - c). Both L and R breakpoints increase by c.
60    void shift_arg(long long c) {
61        addL += c;
62        addR += c;
63    }
64
65    // Prefix minimum closure: g(x) = min_{y <= x} f(y). Drop all right hinges.
66    void chmin_prefix() {
67        while (!R.empty()) R.pop();
68    }
69
70    // Suffix minimum closure: g(x) = min_{y >= x} f(y). Drop all left hinges.
71    void chmin_suffix() {
72        while (!L.empty()) L.pop();
73    }
74
75    // Query current minimum value of f.
76    long long min_value() const { return min_f; }
77
78    // Minimizer interval [argmin_left, argmin_right]. May be (-INF, INF) if both empty.
79    pair<long long, long long> argmin_interval() const {
80        return { topL(), topR() };
81    }
82};
83
84int main() {
85    ios::sync_with_stdio(false);
86    cin.tie(nullptr);
87
88    SlopeTrick st;
89
90    // Build f(x) = |x-3| + |x-7|
91    st.add_abs(3);
92    st.add_abs(7);
93
94    cout << "min f = " << st.min_value() << "\n"; // minimizer is any x in [3,7]
95    auto [L, R] = st.argmin_interval();
96    cout << "argmin interval: [" << L << ", " << R << "]\n";
97
98    // Shift: g(x) = f(x-2) => argmin interval shifts by +2
99    st.shift_arg(2);
100    auto [L2, R2] = st.argmin_interval();
101    cout << "after shift by +2, argmin interval: [" << L2 << ", " << R2 << "]\n";
102
103    // Prefix-min closure: h(x) = min_{y <= x} g(y) drops right slope
104    st.chmin_prefix();
105    auto [L3, R3] = st.argmin_interval();
106    cout << "after prefix-min, argmin interval: [" << L3 << ", " << R3 << "]\n"; // R becomes +INF
107
108    return 0;
109}
110

This is a compact Slope Trick implementation with the canonical operations needed for many convex DP problems. It stores hinge breakpoints in two heaps with lazy offsets so shifts are O(1). The example shows adding two absolute-value terms, querying the minimizer interval, shifting the argument, and taking a prefix minimum.

Time: Each add_abs is O(log n); shift and chmin_prefix/suffix are O(1).Space: O(n) for n total add operations.
Minimum cost to make a sequence non-decreasing (L1 cost)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SlopeTrick {
5    static constexpr long long INF = (1LL<<60);
6    long long min_f = 0, addL = 0, addR = 0;
7    priority_queue<long long> L; // stores (l - addL)
8    priority_queue<long long, vector<long long>, greater<long long>> R; // stores (r - addR)
9    inline long long topL() const { return L.empty()? -INF : L.top() + addL; }
10    inline long long topR() const { return R.empty()?  INF : R.top() + addR; }
11    inline void pushL(long long x) { L.push(x - addL); }
12    inline void pushR(long long x) { R.push(x - addR); }
13    void add_a_minus_x(long long a){ if(!R.empty() && a > topR()){ min_f += a - topR(); long long t=topR(); R.pop(); pushL(t); pushR(a);} else pushL(a);}    
14    void add_x_minus_a(long long a){ if(!L.empty() && a < topL()){ min_f += topL() - a; long long t=topL(); L.pop(); pushR(t); pushL(a);} else pushR(a);}    
15    void add_abs(long long a){ add_a_minus_x(a); add_x_minus_a(a);}    
16    void chmin_prefix(){ while(!R.empty()) R.pop(); }
17    long long min_value() const { return min_f; }
18};
19
20// Problem: Given a[1..n], choose non-decreasing b[1..n] minimizing sum |a[i] - b[i]|.
21// DP: f_i(x) = |x - a[i]| + min_{y <= x} f_{i-1}(y). Slope Trick encodes f_i.
22
23int main(){
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    int n; 
28    if(!(cin >> n)) return 0;
29    vector<long long> a(n);
30    for(int i=0;i<n;i++) cin >> a[i];
31
32    SlopeTrick st; // f_0(x) = 0
33    for(int i=0;i<n;i++){
34        st.chmin_prefix();    // enforce b_{i-1} <= b_i
35        st.add_abs(a[i]);     // add |x - a[i]|
36    }
37
38    cout << st.min_value() << "\n";
39    return 0;
40}
41

We implement the classic O(n log n) solution via Slope Trick. The DP recurrence is f_i(x) = |x βˆ’ a_i| + min_{y ≀ x} f_{iβˆ’1}(y). Each iteration applies a prefix minimum and then adds a V-shaped cost centered at a[i]. The data structure maintains the convex function implicitly; the final minimum is st.min_value().

Time: O(n log n): one add_abs per element; chmin_prefix is O(1) per step.Space: O(n) for n hinge insertions.
Minimum cost to make a sequence non-increasing (symmetric variant)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SlopeTrick {
5    static constexpr long long INF = (1LL<<60);
6    long long min_f = 0, addL = 0, addR = 0;
7    priority_queue<long long> L; // (l - addL)
8    priority_queue<long long, vector<long long>, greater<long long>> R; // (r - addR)
9    inline long long topL() const { return L.empty()? -INF : L.top() + addL; }
10    inline long long topR() const { return R.empty()?  INF : R.top() + addR; }
11    inline void pushL(long long x) { L.push(x - addL); }
12    inline void pushR(long long x) { R.push(x - addR); }
13    void add_a_minus_x(long long a){ if(!R.empty() && a > topR()){ min_f += a - topR(); long long t=topR(); R.pop(); pushL(t); pushR(a);} else pushL(a);}    
14    void add_x_minus_a(long long a){ if(!L.empty() && a < topL()){ min_f += topL() - a; long long t=topL(); L.pop(); pushR(t); pushL(a);} else pushR(a);}    
15    void add_abs(long long a){ add_a_minus_x(a); add_x_minus_a(a);}    
16    void chmin_suffix(){ while(!L.empty()) L.pop(); }
17    long long min_value() const { return min_f; }
18};
19
20// Problem: Given a[1..n], choose non-increasing b[1..n] minimizing sum |a[i] - b[i]|.
21// DP: f_i(x) = |x - a[i]| + min_{y >= x} f_{i-1}(y). Take suffix min each step.
22
23int main(){
24    ios::sync_with_stdio(false);
25    cin.tie(nullptr);
26
27    int n; 
28    if(!(cin >> n)) return 0;
29    vector<long long> a(n);
30    for(int i=0;i<n;i++) cin >> a[i];
31
32    SlopeTrick st; // f_0(x) = 0
33    for(int i=0;i<n;i++){
34        st.chmin_suffix();    // enforce b_{i-1} >= b_i
35        st.add_abs(a[i]);     // add |x - a[i]|
36    }
37
38    cout << st.min_value() << "\n";
39    return 0;
40}
41

This mirrors the non-decreasing case but enforces b_{iβˆ’1} β‰₯ b_i by applying a suffix-min closure before adding each |x βˆ’ a[i]|. The data structure symmetry allows the same add_abs implementation.

Time: O(n log n)Space: O(n)