Изменения
→Для чего нужна нижняя огибающая множества прямых
4) Выделим множество точек <tex>(x0, y0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x0) < y0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек (x, convex(x)) представляет собой выпуклую вверх функцию.
==Для чего нужна нижняя огибающая Цель нижней огибающей множества прямых==Пусть мы считаем динамику для <tex>i</tex>-го дерева. Его задает <tex>x[i]</tex>. Итак, нам нужно для данного <tex>x[i]</tex> найти <tex>min_\min\limits_{j=0..i-1}(k[j]*\cdot x[i] + b[i]) = min_\min\limits_{j=0..i-1}(y[j](x[i]))</tex>. Это выражение есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <tex>x = x[i]</tex>, можно найти бинарным поиском. Это потребует <tex>O(logn\log(n))</tex> времени на поиск такого <tex>j</tex>, что <tex>dp[i] = k[j] * \cdot x[i] + b[j]</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять <tex>i</tex>-ю прямую после того, как мы посчитали <tex>b[i] = dp[i]</tex>.
Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex>k[]</tex> и <tex>b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>i</tex>-тую) прямую в множество. Пусть сейчас в множестве лежит <tex>sz</tex> прямых (нумерация с 1). Пусть <tex>(xL, yL)</tex> - точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(xR, yR)</tex> - точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>-й. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>xL</tex> и <tex>xR</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(xL >= xR)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо <tex>xL</tex> не станет меньше <tex>xR.</tex>
Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1 </math> раз добавится в стек и максимум <math>1 </math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
Корректность : достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.
