Convex hull trick (Li Chao)
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Mantiene un conjunto de rectas y responde el mínimo (o máximo) en un punto, para optimizar DPs de la forma dp[i] = min_j (m_j·x_i + b_j).
Complejidad: Agregar recta y consultar: O(log rango).
Cuándo usarlo
DPs de costo lineal con transiciones tipo recta; cuando los coeficientes no vienen ordenados (Li Chao es más general que el CHT monótono).
Implementación recomendada (C++)
struct LiChao { // mínimo de un conjunto de rectas en [0, n)
struct Line { long long m, b; long long operator()(long long x) const { return m*x + b; } };
int n; vector<Line> t; vector<char> has;
LiChao(int n) : n(n), t(4*n), has(4*n, 0) {}
void add(Line nw, int node, int l, int r) {
if (!has[node]) { t[node] = nw; has[node] = 1; return; }
int m = (l + r) / 2;
bool left = nw(l) < t[node](l), mid = nw(m) < t[node](m);
// la recta que gana en el punto medio se queda en el nodo; la otra solo
// puede ganar en la mitad donde ambas se cruzan
if (mid) swap(t[node], nw);
if (l == r) return;
if (left != mid) add(nw, 2*node, l, m);
else add(nw, 2*node+1, m+1, r);
}
long long query(long long x, int node, int l, int r) {
if (!has[node]) return LLONG_MAX;
long long res = t[node](x);
if (l == r) return res;
int m = (l + r) / 2;
return min(res, x <= m ? query(x, 2*node, l, m) : query(x, 2*node+1, m+1, r));
}
void add(long long m, long long b) { add({m, b}, 1, 0, n-1); }
long long query(long long x) { return query(x, 1, 0, n-1); }
};
// Coordenadas enteras dispersas: dividir por índices, evaluar en los x originales.
struct LiChaoDiscreto {
using Line = LiChao::Line;
vector<long long> xs; vector<Line> t; vector<char> has;
explicit LiChaoDiscreto(vector<long long> coords) : xs(move(coords)) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
assert(!xs.empty());
t.resize(4*xs.size()); has.assign(4*xs.size(), 0);
}
void add(Line nw, int node, int l, int r) {
if (!has[node]) { t[node] = nw; has[node] = 1; return; }
int m = (l+r)/2;
bool left = nw(xs[l]) < t[node](xs[l]);
bool mid = nw(xs[m]) < t[node](xs[m]);
if (mid) swap(t[node], nw);
if (l == r) return;
if (left != mid) add(nw, 2*node, l, m);
else add(nw, 2*node+1, m+1, r);
}
long long query(int i, int node, int l, int r) const {
if (!has[node]) return LLONG_MAX;
long long res = t[node](xs[i]);
if (l == r) return res;
int m = (l+r)/2;
return min(res, i <= m ? query(i, 2*node, l, m)
: query(i, 2*node+1, m+1, r));
}
void add(long long m, long long b) { add({m,b}, 1, 0, (int)xs.size()-1); }
long long query(long long x) const {
int i = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
assert(i < (int)xs.size() && xs[i] == x); // x debe estar registrado
return query(i, 1, 0, (int)xs.size()-1);
}
};⚠️ Notas
LiChao(n) requiere n > 0 y consultas enteras en [0,n). No reemplaces x por su índice comprimido: cambia mx+b. Para coordenadas dispersas usa LiChaoDiscreto({100,1000}): registra todas las x antes de insertar y consulta query(100), no query(0). Con y=x e y=50 devuelve 50. La variante discreta usa O(q) memoria y O(log q) por operación, más O(q log q) al ordenar q coordenadas. Ambas devuelven LLONG_MAX sin rectas. Todos los productos mx y sumas m*x+b deben caber en long long. Para máximo, negar coeficientes requiere además que esa negación sea representable. Prueba que tu DP tiene transiciones lineales.