Li Chao Tree (CHT)
O(log C) per line / queryMaintain a set of lines y = kx + m and answer 'minimum y at x' queries: the convex hull trick without any monotonicity requirements on slopes or queries. Each tree node keeps the line that wins at its segment's midpoint; inserting recurses into the half where the loser might still win. This is what turns dp[i] = min over j of (dp[j] + k[j]·x[i] + m[j]) from O(n²) into O(n log C).
// use it on
Codeforces 319C: Kalila and Dimna in the Logging Industry ↗
dp[i] = min over j of (dp[j] + b[j]·a[i]): insert line (b[j], dp[j]) after computing each dp[j], query at a[i]. The canonical CHT-as-DP-speedup problem.
// the code
typedef long long ll;
struct LiChao { // minimum at integer x in [lo, hi); sparse, big domains OK
ll lo, hi;
unordered_map<ll, pair<ll, ll>> line; // heap node -> line (k, m)
LiChao(ll lo, ll hi) : lo(lo), hi(hi) {}
ll val(pair<ll, ll> f, ll x) { return f.first * x + f.second; }
void add(ll k, ll m) {
pair<ll, ll> nw = {k, m};
ll v = 1, l = lo, r = hi;
while (true) {
if (!line.count(v)) { line[v] = nw; return; }
ll mid = (l + r) / 2;
if (val(nw, mid) < val(line[v], mid)) swap(nw, line[v]);
if (r - l == 1) return;
if (val(nw, l) < val(line[v], l)) { v = 2 * v; r = mid; }
else if (val(nw, r - 1) < val(line[v], r - 1)) { v = 2 * v + 1; l = mid; }
else return; // loser is beaten everywhere here
}
}
ll query(ll x) {
ll v = 1, l = lo, r = hi, res = LLONG_MAX;
while (true) {
if (line.count(v)) res = min(res, val(line[v], x));
if (r - l == 1) return res;
ll mid = (l + r) / 2;
if (x < mid) { v = 2 * v; r = mid; }
else { v = 2 * v + 1; l = mid; }
}
}
};
// careful: k*x + m must fit in long long at the domain edges// more digits & optimization