Convex Hull Trick и Li Chao tree: оптимизация ДП с O(n²) до O(n log n)

Convex Hull Trick простыми словами: как ускорить ДП вида dp[i] = min(dp[j] + a_j·x_i + b_j), монотонный случай с деком, бинпоиск по оболочке и дерево Li Chao. Код на Python и разбор.

9 мин чтенияалгоритмы · динамическое программирование · оптимизация · python

Коротко

ВариантУсловиеДобавлениеЗапрос
Наивное ДПлюбое—O(n)O(n)
CHT с декомнаклоны монотонны и запросы монотонныO(1)O(1) аморт.O(1)O(1) аморт.
CHT с бинпоискомнаклоны монотонны, запросы в любом порядкеO(1)O(1) аморт.O(log⁡n)O(\log n)
Li Chao treeничего не нужно, x — целые из известного диапазонаO(log⁡C)O(\log C)O(log⁡C)O(\log C)
  • Когда применять: переход ДП имеет вид dp[i]=min⁡j<i(dp[j]+aj⋅xi+bj)dp[i] = \min_{j<i}(dp[j] + a_j \cdot x_i + b_j) — то есть слагаемое, зависящее одновременно от i и j, является произведением «что-то от j» на «что-то от i».
  • Главная идея: каждое j — это прямая y=ajx+bjy = a_j x + b_j, а вычисление dp[i] — поиск минимума среди всех прямых в точке x=xix = x_i. Минимум набора прямых — выпуклая ломаная, и большинство прямых на неё никогда не попадает.
  • Итог: O(n2)→O(n)O(n^2) \to O(n) или O(nlog⁡n)O(n \log n).

Это не та выпуклая оболочка

Сразу разведём понятия. В блоге есть статья про выпуклую оболочку точек — алгоритмы Эндрю и Грэхема, которые строят минимальный выпуклый многоугольник вокруг набора точек. Это задача вычислительной геометрии.

Convex Hull Trick (CHT) — приём оптимизации динамики. Здесь у нас не точки, а прямые, и ищем мы не многоугольник, а нижнюю огибающую — ломаную, которая в каждой точке x равна минимуму из всех прямых. Название пошло из того, что огибающая прямых двойственна выпуклой оболочке точек (aj,bj)(a_j, b_j), и те же самые векторные проверки «выкидываем лишнее» работают и там, и там. Но код, задачи и способ мышления разные: знать одно — не значит знать другое.

Откуда берутся прямые в ДП

Возьмём классику — задачу Frog 3 из AtCoder Educational DP Contest. Есть n камней с высотами h0<h1<⋯<hn−1h_0 < h_1 < \dots < h_{n-1} (строго возрастают). Лягушка стоит на камне 0 и хочет попасть на последний. Прыжок с j на i (где j<ij < i) стоит (hi−hj)2+C(h_i - h_j)^2 + C. Найти минимальную суммарную стоимость. Ограничения: n≤2⋅105n \le 2 \cdot 10^5, C≤1012C \le 10^{12}.

Динамика очевидна:

dp[i]=min⁡j<i(dp[j]+(hi−hj)2+C)dp[i] = \min_{j < i} \big( dp[j] + (h_i - h_j)^2 + C \big)
def frog_naive(h, C): n = len(h) dp = [0] * n for i in range(1, n): dp[i] = min(dp[j] + (h[i] - h[j]) ** 2 + C for j in range(i)) return dp[-1]

Это O(n2)O(n^2) — для n=2⋅105n = 2 \cdot 10^5 около 2⋅10102 \cdot 10^{10} операций, не уложимся. Раскроем квадрат:

dp[j]+hi2−2hihj+hj2+Cdp[j] + h_i^2 - 2 h_i h_j + h_j^2 + C

Разложим слагаемые по тому, от чего они зависят:

  • hi2+Ch_i^2 + C — только от i. Выносим за минимум.
  • −2hj⋅hi-2 h_j \cdot h_i — произведение «от j» на «от i».
  • dp[j]+hj2dp[j] + h_j^2 — только от j.

Получаем:

dp[i]=hi2+C+min⁡j<i(−2hj⏟kj⋅hi+dp[j]+hj2⏟bj)dp[i] = h_i^2 + C + \min_{j < i} \big( \underbrace{-2h_j}_{k_j} \cdot h_i + \underbrace{dp[j] + h_j^2}_{b_j} \big)

Каждому j соответствует прямая y=kjx+bjy = k_j x + b_j. Чтобы посчитать dp[i], нужно найти минимум всех уже добавленных прямых в точке x=hix = h_i. После этого добавляем прямую для самого i. Вот и вся структура: добавить прямую и спросить минимум в точке.

Этот приём переразложения — главный навык. Любой переход, где взаимодействие i и j сводится к одному произведению f(j)⋅g(i)f(j) \cdot g(i), превращается в задачу о прямых.

Почему большинство прямых не нужны

Нарисуйте на листке три прямые с убывающими наклонами. Минимум из них — ломаная, выпуклая вверх (каждое следующее звено идёт круче вниз). Если средняя прямая проходит выше точки пересечения двух крайних, она нигде не бывает минимальной — её можно выбросить навсегда.

Формально: пусть наклоны k1>k2>k3k_1 > k_2 > k_3. Прямые 1 и 2 пересекаются в

x12=b2−b1k1−k2,x13=b3−b1k1−k3x_{12} = \frac{b_2 - b_1}{k_1 - k_2}, \qquad x_{13} = \frac{b_3 - b_1}{k_1 - k_3}

При x→−∞x \to -\infty выигрывает прямая с большим наклоном (она уходит вниз сильнее всех), при x→+∞x \to +\infty — с меньшим. Значит, на огибающей прямые идут слева направо в порядке убывания наклона. Прямая 2 нужна, только если она «успевает» стать минимальной между первой и третьей, то есть x12<x13x_{12} < x_{13}. Если же x13≤x12x_{13} \le x_{12}, третья обгоняет первую раньше, чем это успевает сделать вторая, — вторая лишняя.

Чтобы не делить (и не получать ошибки округления), умножим на положительные знаменатели:

def bad(l1, l2, l3): # l2 не нужна, если l1 и l3 пересекаются не правее, чем l1 и l2 (k1, b1), (k2, b2), (k3, b3) = l1, l2, l3 return (b3 - b1) * (k1 - k2) <= (b2 - b1) * (k1 - k3) def value(line, x): k, b = line return k * x + b

Это ровно та же проверка, что и «поворот направо» в алгоритме Эндрю, только записанная для прямых.

Монотонный случай: дек за O(n)

В Frog 3 нам повезло дважды:

  1. Наклоны убывают. kj=−2hjk_j = -2h_j, а hh возрастает, значит каждая новая прямая круче предыдущих. Новая прямая всегда встаёт в правый конец огибающей.
  2. Запросы возрастают. Мы спрашиваем в точках x=hix = h_i, которые тоже растут. Значит, если прямая на левом краю перестала быть лучшей в точке hih_i, она не станет лучшей и дальше.

Отсюда алгоритм с двусторонней очередью (подробнее о структуре — в статье про дек):

  • Добавление: пока последние две прямые и новая образуют «лишнюю середину» — снимаем последнюю с правого конца. Потом кладём новую.
  • Запрос: пока вторая слева прямая в точке x не хуже первой — снимаем первую с левого конца. Ответ — первая прямая.

Каждая прямая попадает в дек один раз и удаляется не больше одного раза, поэтому всё вместе работает за O(n)O(n). Это тот же принцип амортизации, что у монотонной очереди.

from collections import deque def frog_cht(h, C): n = len(h) dp = [0] * n hull = deque() hull.append((-2 * h[0], dp[0] + h[0] ** 2)) for i in range(1, n): x = h[i] # Левые прямые, которые уже проиграли, больше не понадобятся while len(hull) >= 2 and value(hull[0], x) >= value(hull[1], x): hull.popleft() dp[i] = value(hull[0], x) + x * x + C line = (-2 * h[i], dp[i] + h[i] ** 2) # Новая прямая может сделать лишними прямые на правом краю while len(hull) >= 2 and bad(hull[-2], hull[-1], line): hull.pop() hull.append(line) return dp[-1] print(frog_cht([1, 2, 3, 4, 5], 6)) # 20

Последняя строка — первый пример из условия: 5 камней высотой 1…5, C=6C = 6. Оптимально прыгнуть 1→3→51 \to 3 \to 5: (4+6)+(4+6)=20(4 + 6) + (4 + 6) = 20.

Разбор на примере

Возьмём h=[1,3,4,7]h = [1, 3, 4, 7], C=5C = 5. Наивное ДП даёт dp=[0,9,14,28]dp = [0, 9, 14, 28]. Проследим, что происходит в деке.

ШагЗапрос xДек до запросаЧто выкинули слеваdp[i]Новая прямая
старт———dp[0] = 0(−2, 1)
i = 13(−2, 1)ничего−6 + 1 + 9 + 5 = 9(−6, 18)
i = 24(−2, 1), (−6, 18)ничего: −7 < −6−7 + 16 + 5 = 14(−8, 30)
i = 37(−2, 1), (−6, 18), (−8, 30)(−2, 1), (−6, 18)−26 + 49 + 5 = 28(−14, …)

Перед добавлением (−8,30)(-8, 30) проверяем, не стала ли (−6,18)(-6, 18) лишней. Пересечение первой и второй — в x=17/4=4,25x = 17/4 = 4{,}25, первой и третьей — в x=29/6≈4,83x = 29/6 \approx 4{,}83. Вторая успевает побыть минимумом на отрезке [4,25; 6][4{,}25;\ 6], поэтому остаётся. А в точке x=7x = 7 лучшей оказывается третья: −56+30=−26-56 + 30 = -26, что соответствует прыжку с камня 2 на камень 3. Ответ 28 совпал с наивным.

Наклоны монотонны, запросы — нет: бинпоиск

Бывает, что прямые приходят по порядку наклонов, а точки запроса — вразнобой. Тогда левый край дека трогать нельзя: прямая, проигравшая в одной точке, может выиграть в следующей. Правый край обслуживаем как раньше, а ответ ищем бинарным поиском: на огибающей значения в точке x сначала убывают, потом возрастают при движении по прямым слева направо, так что ищем первую прямую, которая лучше следующей.

class MonotoneHull: """Нижняя огибающая для минимума: прямые добавляются по убыванию k.""" def __init__(self): self.lines = [] def add(self, k, b): if self.lines and self.lines[-1][0] == k: # Параллельные прямые: оставляем ту, что ниже if self.lines[-1][1] <= b: return self.lines.pop() line = (k, b) while len(self.lines) >= 2 and bad(self.lines[-2], self.lines[-1], line): self.lines.pop() self.lines.append(line) def query(self, x): lo, hi = 0, len(self.lines) - 1 while lo < hi: mid = (lo + hi) // 2 if value(self.lines[mid], x) >= value(self.lines[mid + 1], x): lo = mid + 1 else: hi = mid return value(self.lines[lo], x)

Обратите внимание на параллельные прямые. В Frog 3 их не бывает (высоты строго возрастают), но в общем случае k1=k2k_1 = k_2 обнуляет знаменатель в рассуждениях про пересечения. Проще обработать их отдельно: из двух параллельных нужна только нижняя.

Запрос — O(log⁡n)O(\log n), добавление — O(1)O(1) амортизированно.

Общий случай: Li Chao tree

А если и наклоны приходят в произвольном порядке? Можно поддерживать огибающую в сбалансированном дереве поиска (так называемый dynamic CHT), но это много аккуратного кода с граничными случаями. На практике почти всегда берут дерево Li Chao — оно короче, его трудно написать с ошибкой, и оно работает для любых прямых.

Требование одно: точки запроса — целые числа из заранее известного диапазона [lo,hi][lo, hi] (или значения, которые можно заранее собрать и сжать в индексы).

Идея

Это дерево отрезков по оси x, где в каждом узле хранится одна прямая — та, что лучше всех в середине отрезка узла среди прямых, «застрявших» в этом узле.

Добавление прямой new в узел с отрезком [lo, hi] и текущей прямой cur:

  1. Посчитать середину mid. Если new лучше cur в mid, поменять их местами: в узле остаётся лучшая в середине.
  2. Две прямые пересекаются не больше одного раза. Значит, проигравшая может быть лучше только на одной из половин — той, где она лучше на краю. Сравниваем в lo: если победитель в lo и победитель в mid разные, точка пересечения слева — спускаем проигравшую в левого ребёнка. Иначе — в правого.
  3. Спуск идёт по одной ветке, поэтому добавление — O(log⁡C)O(\log C), где C=hi−lo+1C = hi - lo + 1.

Запрос в точке x: идём от корня к листу, содержащему x, и берём минимум по всем прямым на пути. Почему этого достаточно: оптимальная в точке x прямая либо осталась в одном из узлов на пути, либо была вытеснена прямой, которая лучше её на всей нужной половине.

INF = float('inf') class LiChao: def __init__(self, lo, hi): self.lo, self.hi = lo, hi self.line = {} # номер узла -> (k, b); узлы создаются по мере надобности def add(self, k, b): node, lo, hi = 1, self.lo, self.hi new = (k, b) while True: cur = self.line.get(node) if cur is None: self.line[node] = new return mid = (lo + hi) // 2 left_better = value(new, lo) < value(cur, lo) mid_better = value(new, mid) < value(cur, mid) if mid_better: self.line[node], new = new, cur if lo == hi: return if left_better != mid_better: node, hi = 2 * node, mid else: node, lo = 2 * node + 1, mid + 1 def query(self, x): node, lo, hi = 1, self.lo, self.hi best = INF while node in self.line: best = min(best, value(self.line[node], x)) if lo == hi: break mid = (lo + hi) // 2 if x <= mid: node, hi = 2 * node, mid else: node, lo = 2 * node + 1, mid + 1 return best

Узлы хранятся в словаре, поэтому диапазон может быть хоть [−109,109][-10^9, 10^9]: реально создаётся не больше одного узла на добавление. Если узла на пути нет, ниже тоже ничего нет — запрос можно останавливать.

Почему условие left_better != mid_better выбирает правильную сторону: после обмена в узле лежит победитель в mid. Если в lo победитель другой, прямые пересеклись на [lo,mid][lo, mid], и проигравшая ещё может быть лучше где-то слева. Если победитель в lo тот же, то слева проигравшая хуже везде (иначе пересечений было бы два), и шанс у неё остаётся только справа.

Шаблон для любого такого ДП

def solve(x, a, b, dp0):
# dp[i] = min_{j<i} dp[j] + a[j] * x[i] + b[j], x[i] в [0, 10**6]
n = len(x)
dp = [0] * n
dp[0] = dp0
tree = LiChao(0, 10**6)
tree.add(a[0], dp[0] + b[0])
for i in range(1, n):
    dp[i] = tree.query(x[i])
    tree.add(a[i], dp[i] + b[i])
return dp

Все три реализации из статьи проверены против наивного $O(n^2)$ на нескольких сотнях случайных тестов, включая отрицательные наклоны и совпадающие значения.

## Какую версию выбирать

- **Наклоны и запросы монотонны** (как в Frog 3) — дек. Это $O(n)$ и самый быстрый вариант.
- **Монотонны только наклоны** — тот же стек плюс бинпоиск.
- **Ничего не монотонно** или нет сил думать о порядке — Li Chao. Работает всегда, когда x целые и диапазон известен, стоит лишний логарифм.
- Li Chao ещё и легко расширяется: можно добавлять не прямые, а **отрезки** (прямая действует только на $[l, r]$) — за $O(\log^2 C)$, а также любые функции, которые попарно пересекаются не больше одного раза.

Для максимума вместо минимума ничего переписывать не нужно: храните прямые $(-k, -b)$ и берите минус от ответа.

## Типичные ошибки

**Не тот порядок наклонов.** Дек-версия выше рассчитана на минимум и **убывающие** наклоны. Если у вас наклоны растут, а нужен минимум, — прямые будут добавляться на левый край, и код молча выдаст неверный ответ. Либо разверните задачу (замена $x \to -x$ меняет знак наклонов), либо возьмите Li Chao.

**Переполнение.** В проверке `bad` перемножаются разности наклонов и свободных членов. В Frog 3 $b_j$ доходит до $\sim 10^{17}$, а произведение — до $10^{23}$, что не влезает в 64 бита. В Python это не проблема, в C++ используйте `__int128` или сравнение в `long double`, в Java — `Math.multiplyHigh` или `BigInteger`. Li Chao здесь удобнее: в нём только вычисление $k x + b$, без произведений разностей.

**Дробные точки пересечения.** Хранить в деке координаты пересечений как `float` соблазнительно, но на больших числах это даёт ошибки сравнения. Сравнивайте перекрёстным умножением, как в `bad`.

**Строгость сравнений.** В запросе `>=` и `>` дают одинаковый ответ — при равенстве неважно, какую из двух прямых взять. А вот в `bad` нужно именно `<=`: так выбрасывается прямая, которая касается огибающей лишь в одной точке. С `<` она останется, ответ не испортится, но если таких прямых много, дек раздувается. Опаснее перепутать знак целиком — тогда выбрасываются нужные прямые.

**Забыли, что x должен быть в диапазоне дерева.** Li Chao с границами $[0, 10^6]$ молча вернёт ерунду для $x = -5$. Задайте диапазон по ограничениям задачи или сожмите все будущие точки запроса заранее.

**Добавили прямую до запроса.** В переходе $j < i$ прямая для `i` должна попасть в структуру **после** вычисления `dp[i]`. Если $j \le i$ — порядок другой, перечитайте условие.

## Где это встречается

На обычных собеседованиях в продуктовые компании CHT спрашивают редко: это олимпиадная техника, и на LeetCode чистых задач на неё почти нет. Зато она встречается на алгоритмических секциях с олимпиадным уклоном, в контестах и в задачах, где интервьюер ждёт, что вы хотя бы назовёте оптимизацию после $O(n^2)$-решения.

Классические задачи для тренировки:

- **Frog 3** (AtCoder Educational DP Contest, задача Z) — разобранная выше, монотонный случай.
- **Commando** (APIO 2010) — $dp[i] = \max_j (dp[j] + a(S_i - S_j)^2 + b(S_i - S_j) + c)$ по префиксным суммам, тоже монотонный случай, но на максимум.
- **Kalila and Dimna in the Logging Industry** (Codeforces 319C) — переход вида $dp[i] = \min_j(dp[j] + b_j \cdot a_i)$.

Как распознать: вы написали $O(n^2)$-динамику с минимумом по `j`, ограничения $n \ge 10^5$, и в формуле перехода есть произведение величины от `j` на величину от `i`. Раскройте скобки, выпишите $k_j$, $b_j$ и $x_i$ — и дальше уже техника. Если перехода такого вида нет, но нужен минимум по отрезку `j`, посмотрите на [монотонную очередь](/blog/monotonic-queue); если состояние двумерное — на [динамику по отрезкам](/blog/interval-dp).

Потренироваться в спокойной обстановке

Все задачи