Slope Trick
(convex/slope_trick.hpp)
- View this file on GitHub
- Last update: 2026-07-07 18:38:36+09:00
- Include:
#include "convex/slope_trick.hpp"
Overview
SlopeTrick<T> maintains a convex piecewise-linear function whose slopes
change by integer units. It supports adding hinge and absolute-value functions,
translations, sliding-window minima, evaluation, function addition, and
min-plus convolution of two slope-trick functions.
The structure stores the breakpoints in two heaps. Most updates take logarithmic time without explicitly constructing the function over its whole domain.
Typical applications include scheduling, sequence adjustment, median costs, and dynamic programs with convex piecewise-linear states.
Complexity Notation
-
Nis the number of breakpoints stored in the current object. -
Mis the number of breakpoints stored in another object passed tomergeormin_plus_convolve.
Represented Function
A new object represents f(x) = 0 for every x.
The template parameter must be a signed arithmetic type. long long is
recommended for integer problems. All values, breakpoint translations, and
intermediate sums must fit in T.
Adding Functions
| Method | Effect |
|---|---|
void add_constant(T c) |
Adds the constant c. |
void add_x_minus_a(T a) |
Adds max(x - a, 0). |
void add_a_minus_x(T a) |
Adds max(a - x, 0). |
void add_abs(T a) |
Adds abs(x - a). |
Each hinge insertion takes amortized $O(\log N)$ time, where N is the current
number of stored breakpoints. add_abs inserts two hinges.
Minimum and Argmin
| Method | Meaning |
|---|---|
T minimum() const |
Minimum function value. |
SlopeTrickArgmin<T> argmin() const |
Closed interval on which the minimum is attained. |
int breakpoint_count() const |
Number of stored unit-slope breakpoints. |
argmin() returns SlopeTrickArgmin<T> with optional left and right
endpoints. An empty left endpoint means the interval is unbounded below; an
empty right endpoint means it is unbounded above.
For the initial constant function, both endpoints are empty.
Translation and Sliding Minimum
shift(delta) replaces the function by
shift(left_delta, right_delta) requires
left_delta <= right_delta and computes
This operation shifts the left and right breakpoint heaps independently and takes $O(1)$ time.
The one-sided variants are:
| Method | Effect |
|---|---|
void shift(T delta) |
Replaces f(x) by f(x - delta). |
void shift(T left_delta, T right_delta) |
Replaces f(x) by a sliding-window minimum. |
void prefix_minimum() / void clear_right()
|
Replaces f(x) by min over y <= x of f(y). |
void suffix_minimum() / void clear_left()
|
Replaces f(x) by min over y >= x of f(y). |
Clearing one side takes linear time in the number of discarded breakpoints.
Evaluation, Merge, and Convolution
T evaluate(T x) const returns f(x) in $O(N)$ time without changing the structure.
This is intended mainly for final answers and debugging; slope trick is useful
because updates and minimum queries avoid evaluating arbitrary points.
void merge(SlopeTrick other) adds the function represented by other to this function.
other is passed by value, so passing an rvalue avoids an extra copy. The
operation takes $O((N+M)\log(N+M))$ time in the worst case.
void min_plus_convolve(SlopeTrick other) replaces the represented function by
where g is the function represented by other. The minimum value becomes
f.minimum() + g.minimum(), and the argmin interval is the Minkowski sum of
the two argmin intervals. If either side is unbounded on the left or right, the
corresponding result side is also unbounded.
SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first, SlopeTrick<T> second)
returns the same convolution as a free function. Both APIs take their
arguments by value, so moving temporary slope tricks avoids extra copies.
The convolution keeps only slope levels that appear in both functions. Its worst-case running time is $O((N+M)\log(N+M))$.
Example
#include "convex/slope_trick.hpp"
#include <iostream>
int main() {
m1une::convex::SlopeTrick<long long> slope;
slope.add_abs(3);
slope.add_x_minus_a(0);
slope.shift(-1, 2);
m1une::convex::SlopeTrick<long long> other;
other.add_abs(5);
auto convolved = m1une::convex::min_plus_convolution(slope, other);
std::cout << convolved.minimum() << "\n";
auto range = convolved.argmin();
if (range.left) std::cout << *range.left << "\n";
}
Required by
Convex All
(convex/all.hpp)
Verified with
Code
#ifndef M1UNE_CONVEX_SLOPE_TRICK_HPP
#define M1UNE_CONVEX_SLOPE_TRICK_HPP 1
#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>
namespace m1une {
namespace convex {
template <class T>
struct SlopeTrickArgmin {
std::optional<T> left;
std::optional<T> right;
};
template <class T>
class SlopeTrick {
static_assert(std::is_arithmetic_v<T> && std::is_signed_v<T>);
T _minimum = T();
T _left_offset = T();
T _right_offset = T();
std::priority_queue<T> _left;
std::priority_queue<T, std::vector<T>, std::greater<T>> _right;
T left_top() const {
return _left.top() + _left_offset;
}
T right_top() const {
return _right.top() + _right_offset;
}
void push_left(T value) {
_left.push(value - _left_offset);
}
void push_right(T value) {
_right.push(value - _right_offset);
}
public:
SlopeTrick() = default;
T minimum() const {
return _minimum;
}
int breakpoint_count() const {
return int(_left.size() + _right.size());
}
SlopeTrickArgmin<T> argmin() const {
SlopeTrickArgmin<T> result;
if (!_left.empty()) result.left = left_top();
if (!_right.empty()) result.right = right_top();
return result;
}
void add_constant(T value) {
_minimum += value;
}
void add_x_minus_a(T a) {
if (!_left.empty() && left_top() > a) {
T old = left_top();
_minimum += old - a;
_left.pop();
push_left(a);
push_right(old);
} else {
push_right(a);
}
}
void add_a_minus_x(T a) {
if (!_right.empty() && right_top() < a) {
T old = right_top();
_minimum += a - old;
_right.pop();
push_right(a);
push_left(old);
} else {
push_left(a);
}
}
void add_abs(T a) {
add_a_minus_x(a);
add_x_minus_a(a);
}
void clear_left() {
_left = std::priority_queue<T>();
}
void clear_right() {
_right = std::priority_queue<T, std::vector<T>, std::greater<T>>();
}
void prefix_minimum() {
clear_right();
}
void suffix_minimum() {
clear_left();
}
void shift(T delta) {
_left_offset += delta;
_right_offset += delta;
}
void shift(T left_delta, T right_delta) {
assert(left_delta <= right_delta);
_left_offset += left_delta;
_right_offset += right_delta;
}
T evaluate(T x) const {
T result = _minimum;
auto left = _left;
while (!left.empty()) {
T breakpoint = left.top() + _left_offset;
if (breakpoint > x) result += breakpoint - x;
left.pop();
}
auto right = _right;
while (!right.empty()) {
T breakpoint = right.top() + _right_offset;
if (x > breakpoint) result += x - breakpoint;
right.pop();
}
return result;
}
void merge(SlopeTrick other) {
add_constant(other._minimum);
while (!other._left.empty()) {
add_a_minus_x(other.left_top());
other._left.pop();
}
while (!other._right.empty()) {
add_x_minus_a(other.right_top());
other._right.pop();
}
}
void min_plus_convolve(SlopeTrick other) {
SlopeTrick result;
result._minimum = _minimum + other._minimum;
while (!_left.empty() && !other._left.empty()) {
result.push_left(left_top() + other.left_top());
_left.pop();
other._left.pop();
}
while (!_right.empty() && !other._right.empty()) {
result.push_right(right_top() + other.right_top());
_right.pop();
other._right.pop();
}
*this = std::move(result);
}
};
template <class T>
SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first,
SlopeTrick<T> second) {
first.min_plus_convolve(std::move(second));
return first;
}
} // namespace convex
} // namespace m1une
#endif // M1UNE_CONVEX_SLOPE_TRICK_HPP#line 1 "convex/slope_trick.hpp"
#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>
namespace m1une {
namespace convex {
template <class T>
struct SlopeTrickArgmin {
std::optional<T> left;
std::optional<T> right;
};
template <class T>
class SlopeTrick {
static_assert(std::is_arithmetic_v<T> && std::is_signed_v<T>);
T _minimum = T();
T _left_offset = T();
T _right_offset = T();
std::priority_queue<T> _left;
std::priority_queue<T, std::vector<T>, std::greater<T>> _right;
T left_top() const {
return _left.top() + _left_offset;
}
T right_top() const {
return _right.top() + _right_offset;
}
void push_left(T value) {
_left.push(value - _left_offset);
}
void push_right(T value) {
_right.push(value - _right_offset);
}
public:
SlopeTrick() = default;
T minimum() const {
return _minimum;
}
int breakpoint_count() const {
return int(_left.size() + _right.size());
}
SlopeTrickArgmin<T> argmin() const {
SlopeTrickArgmin<T> result;
if (!_left.empty()) result.left = left_top();
if (!_right.empty()) result.right = right_top();
return result;
}
void add_constant(T value) {
_minimum += value;
}
void add_x_minus_a(T a) {
if (!_left.empty() && left_top() > a) {
T old = left_top();
_minimum += old - a;
_left.pop();
push_left(a);
push_right(old);
} else {
push_right(a);
}
}
void add_a_minus_x(T a) {
if (!_right.empty() && right_top() < a) {
T old = right_top();
_minimum += a - old;
_right.pop();
push_right(a);
push_left(old);
} else {
push_left(a);
}
}
void add_abs(T a) {
add_a_minus_x(a);
add_x_minus_a(a);
}
void clear_left() {
_left = std::priority_queue<T>();
}
void clear_right() {
_right = std::priority_queue<T, std::vector<T>, std::greater<T>>();
}
void prefix_minimum() {
clear_right();
}
void suffix_minimum() {
clear_left();
}
void shift(T delta) {
_left_offset += delta;
_right_offset += delta;
}
void shift(T left_delta, T right_delta) {
assert(left_delta <= right_delta);
_left_offset += left_delta;
_right_offset += right_delta;
}
T evaluate(T x) const {
T result = _minimum;
auto left = _left;
while (!left.empty()) {
T breakpoint = left.top() + _left_offset;
if (breakpoint > x) result += breakpoint - x;
left.pop();
}
auto right = _right;
while (!right.empty()) {
T breakpoint = right.top() + _right_offset;
if (x > breakpoint) result += x - breakpoint;
right.pop();
}
return result;
}
void merge(SlopeTrick other) {
add_constant(other._minimum);
while (!other._left.empty()) {
add_a_minus_x(other.left_top());
other._left.pop();
}
while (!other._right.empty()) {
add_x_minus_a(other.right_top());
other._right.pop();
}
}
void min_plus_convolve(SlopeTrick other) {
SlopeTrick result;
result._minimum = _minimum + other._minimum;
while (!_left.empty() && !other._left.empty()) {
result.push_left(left_top() + other.left_top());
_left.pop();
other._left.pop();
}
while (!_right.empty() && !other._right.empty()) {
result.push_right(right_top() + other.right_top());
_right.pop();
other._right.pop();
}
*this = std::move(result);
}
};
template <class T>
SlopeTrick<T> min_plus_convolution(SlopeTrick<T> first,
SlopeTrick<T> second) {
first.min_plus_convolve(std::move(second));
return first;
}
} // namespace convex
} // namespace m1une