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.

🔗 Relacionados