Изменения

==Для чего нужна нижняя ошибающая огибающая множества прямых== Пусть мы считаем динамику для <mathtex>i</mathtex>-го дерева. Его задает <mathtex>x[i]</mathtex>. Итак, нам нужно для данного <mathtex>x[i]</mathtex> найти <mathtex>min_{j=0..i-1}(k[j]*x[i] + b[i]) = min_{j=0..i-1}(y[j](x[i]))</mathtex>. Это выражение есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <mathtex>x = x[i]</mathtex>, можно найти бинарным поиском. Это потребует <mathtex>O(logn)</mathtex> времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться поддерживать множество прямых и быстро добавлять <mathtex>i</mathtex>-ю прямую после того, как мы посчитали <mathtex>b[i] = dp[i]</mathtex>.

Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <mathtex>k[]</mathtex> и <mathtex>b[]</mathtex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<mathtex>i</mathtex>-тую) прямую в множество. Пусть сейчас в множестве лежит <mathtex>sz</mathtex> прямых (нумерация с 1). Пусть <mathtex>(xL, yL)</mathtex> - точка пересечения <mathtex>sz - 1</mathtex>-й прямой множества и <mathtex>sz</mathtex>-й, а <mathtex>(xR, yR)</mathtex> - точка пересечения новой прямой, которую мы хотим добавить в конец множества и <mathtex>sz</mathtex>-й. Нас будут интересовать только их <mathtex>x</mathtex>-овые координаты <mathtex>xL</mathtex> и <mathtex>xR</mathtex>, соответственно. Если оказалось, что новая прямая пересекает <mathtex>sz</mathtex>-ю прямую выпуклой оболочки позже, чем <mathtex>sz</mathtex>-я <mathtex>sz - 1</mathtex>-ю, т.е. <mathtex>(xL >= xR)</mathtex>, то <mathtex>sz</mathtex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо <mathtex>xL</mathtex> не станет меньше <mathtex>xR.</mathtex>

Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет <mathtex>O(n)</mathtex> суммарно.

Корректность : достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.

[[Файл:picture2convexhull.png]]

Доказательство : Пусть <mathtex>Y(x) = Kx + B</mathtex> - уравнение новой прямой, <mathtex>y[i](x) = K[i]x + B[i]</mathtex> - уравнения прямых множества. Тогда т.к. <mathtex>K < K[sz]</mathtex>, то при <tex>x \in [- \infty; xR] : y[sz](x) <= Y(x)</tex>, а т.к. <mathtex> K[sz] < K[sz - 1]</mathtex>, то при <tex>x \in [xL; + \infty] : y[sz - 1](x) >= y[sz](x)</tex>. Если <mathtex>xL < xR</mathtex>, то при <tex>x \in [xL; xR] : y[sz - 1] >= y[sz](x) и Y(x) >= y[sz](x)</tex>, т.е. на отрезке <mathtex>[xL; xR]</mathtex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <mathtex>xL > xR</mathtex>, то она ниже всех на отрезке <tex>[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества