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 и разбор.
Коротко
| Вариант | Условие | Добавление | Запрос |
|---|---|---|---|
| Наивное ДП | любое | — | |
| CHT с деком | наклоны монотонны и запросы монотонны | аморт. | аморт. |
| CHT с бинпоиском | наклоны монотонны, запросы в любом порядке | аморт. | |
| Li Chao tree | ничего не нужно, x — целые из известного диапазона |
- Когда применять: переход ДП имеет вид — то есть слагаемое, зависящее одновременно от
iиj, является произведением «что-то от j» на «что-то от i». - Главная идея: каждое
j— это прямая , а вычислениеdp[i]— поиск минимума среди всех прямых в точке . Минимум набора прямых — выпуклая ломаная, и большинство прямых на неё никогда не попадает. - Итог: или .
Это не та выпуклая оболочка
Сразу разведём понятия. В блоге есть статья про выпуклую оболочку точек — алгоритмы Эндрю и Грэхема, которые строят минимальный выпуклый многоугольник вокруг набора точек. Это задача вычислительной геометрии.
Convex Hull Trick (CHT) — приём оптимизации динамики. Здесь у нас не точки, а прямые, и ищем мы не многоугольник, а нижнюю огибающую — ломаную, которая в каждой точке x равна минимуму из всех прямых. Название пошло из того, что огибающая прямых двойственна выпуклой оболочке точек , и те же самые векторные проверки «выкидываем лишнее» работают и там, и там. Но код, задачи и способ мышления разные: знать одно — не значит знать другое.
Откуда берутся прямые в ДП
Возьмём классику — задачу Frog 3 из AtCoder Educational DP Contest. Есть n камней с высотами (строго возрастают). Лягушка стоит на камне 0 и хочет попасть на последний. Прыжок с j на i (где ) стоит . Найти минимальную суммарную стоимость. Ограничения: , .
Динамика очевидна:
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]
Это — для около операций, не уложимся. Раскроем квадрат:
Разложим слагаемые по тому, от чего они зависят:
- — только от
i. Выносим за минимум. - — произведение «от j» на «от i».
- — только от
j.
Получаем:
Каждому j соответствует прямая . Чтобы посчитать dp[i], нужно найти минимум всех уже добавленных прямых в точке . После этого добавляем прямую для самого i. Вот и вся структура: добавить прямую и спросить минимум в точке.
Этот приём переразложения — главный навык. Любой переход, где взаимодействие i и j сводится к одному произведению , превращается в задачу о прямых.
Почему большинство прямых не нужны
Нарисуйте на листке три прямые с убывающими наклонами. Минимум из них — ломаная, выпуклая вверх (каждое следующее звено идёт круче вниз). Если средняя прямая проходит выше точки пересечения двух крайних, она нигде не бывает минимальной — её можно выбросить навсегда.
Формально: пусть наклоны . Прямые 1 и 2 пересекаются в
При выигрывает прямая с большим наклоном (она уходит вниз сильнее всех), при — с меньшим. Значит, на огибающей прямые идут слева направо в порядке убывания наклона. Прямая 2 нужна, только если она «успевает» стать минимальной между первой и третьей, то есть . Если же , третья обгоняет первую раньше, чем это успевает сделать вторая, — вторая лишняя.
Чтобы не делить (и не получать ошибки округления), умножим на положительные знаменатели:
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 нам повезло дважды:
- Наклоны убывают. , а возрастает, значит каждая новая прямая круче предыдущих. Новая прямая всегда встаёт в правый конец огибающей.
- Запросы возрастают. Мы спрашиваем в точках , которые тоже растут. Значит, если прямая на левом краю перестала быть лучшей в точке , она не станет лучшей и дальше.
Отсюда алгоритм с двусторонней очередью (подробнее о структуре — в статье про дек):
- Добавление: пока последние две прямые и новая образуют «лишнюю середину» — снимаем последнюю с правого конца. Потом кладём новую.
- Запрос: пока вторая слева прямая в точке x не хуже первой — снимаем первую с левого конца. Ответ — первая прямая.
Каждая прямая попадает в дек один раз и удаляется не больше одного раза, поэтому всё вместе работает за . Это тот же принцип амортизации, что у монотонной очереди.
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, . Оптимально прыгнуть : .
Разбор на примере
Возьмём , . Наивное ДП даёт . Проследим, что происходит в деке.
| Шаг | Запрос x | Дек до запроса | Что выкинули слева | dp[i] | Новая прямая |
|---|---|---|---|---|---|
| старт | — | — | — | dp[0] = 0 | (−2, 1) |
| i = 1 | 3 | (−2, 1) | ничего | −6 + 1 + 9 + 5 = 9 | (−6, 18) |
| i = 2 | 4 | (−2, 1), (−6, 18) | ничего: −7 < −6 | −7 + 16 + 5 = 14 | (−8, 30) |
| i = 3 | 7 | (−2, 1), (−6, 18), (−8, 30) | (−2, 1), (−6, 18) | −26 + 49 + 5 = 28 | (−14, …) |
Перед добавлением проверяем, не стала ли лишней. Пересечение первой и второй — в , первой и третьей — в . Вторая успевает побыть минимумом на отрезке , поэтому остаётся. А в точке лучшей оказывается третья: , что соответствует прыжку с камня 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 их не бывает (высоты строго возрастают), но в общем случае обнуляет знаменатель в рассуждениях про пересечения. Проще обработать их отдельно: из двух параллельных нужна только нижняя.
Запрос — , добавление — амортизированно.
Общий случай: Li Chao tree
А если и наклоны приходят в произвольном порядке? Можно поддерживать огибающую в сбалансированном дереве поиска (так называемый dynamic CHT), но это много аккуратного кода с граничными случаями. На практике почти всегда берут дерево Li Chao — оно короче, его трудно написать с ошибкой, и оно работает для любых прямых.
Требование одно: точки запроса — целые числа из заранее известного диапазона (или значения, которые можно заранее собрать и сжать в индексы).
Идея
Это дерево отрезков по оси x, где в каждом узле хранится одна прямая — та, что лучше всех в середине отрезка узла среди прямых, «застрявших» в этом узле.
Добавление прямой new в узел с отрезком [lo, hi] и текущей прямой cur:
- Посчитать середину
mid. Еслиnewлучшеcurвmid, поменять их местами: в узле остаётся лучшая в середине. - Две прямые пересекаются не больше одного раза. Значит, проигравшая может быть лучше только на одной из половин — той, где она лучше на краю. Сравниваем в
lo: если победитель вloи победитель вmidразные, точка пересечения слева — спускаем проигравшую в левого ребёнка. Иначе — в правого. - Спуск идёт по одной ветке, поэтому добавление — , где .
Запрос в точке 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
Узлы хранятся в словаре, поэтому диапазон может быть хоть : реально создаётся не больше одного узла на добавление. Если узла на пути нет, ниже тоже ничего нет — запрос можно останавливать.
Почему условие left_better != mid_better выбирает правильную сторону: после обмена в узле лежит победитель в mid. Если в lo победитель другой, прямые пересеклись на , и проигравшая ещё может быть лучше где-то слева. Если победитель в 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).