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