Персистентный Convex Hull Trick
Во многих задачах на динамическое программирование используется “Convex Hull Trick” (CHT), то есть способ быстрого пересчета динамики как максимума или минимума линейных функций. Однако минусом этой техники является ее амортизированность: хранится стек прямых из выпуклой оболочки, и при добавлении новой прямой удаляются все бесполезные прямые с вершины стека. Одна конкретная такая операция может занимать $O(n)$ времени. В результате чего обычный convex hull trick нельзя сделать персистентным или использовать откаты. Для решения этой проблемы обычно используют дерево Ли Чао, которое является неамортизированной альтернативой CHT. В этой главе мы рассмотрим, как легко можно сделать персистентным сам convex hull trick.
Нам нужно научиться за неамортизированное время удалять большое количество элементов с вершины стека (в принципе, предложенный алгоритм подходит не только конкретно для CHT). При помощи бинпоиска мы могли бы найти последнюю прямую на стеке, которую нужно оставить, но не понятно, как удалить все ненужные прямые быстро. Однако мы все равно хотим сделать наш стек персистентным, поэтому не будем ничего удалять, а создадим новую ветку. То есть вместо стека у нас будет дерево, и если мы находимся в какой-то вершине, то текущий стек — это все элементы на пути до корня. Это сразу решает и проблему амортизированности, и проблему персистентности. Однако появляется новая проблема — и при поиске последней прямой, которую нужно оставить, и при поиске минимума линейных функций в точке, мы используем бинпоиск по стеку. В дереве мы этого сделать, к сожалению, не можем.
Для этого давайте в дереве хранить двоичные подъемы. Тогда вместо бинпоиска можно использовать подъем по дереву при помощи двоичных подъемов, который используется при поиске LA и LCA. Так как после каждой итерации добавляется ровно одна вершина в дерево как лист, то двоичные подъемы можно пересчитывать на лету для новой вершины. Асимптотика получившегося алгоритма — $O((n + q) \log n)$ на $n$ запросов добавления прямых и $q$ запросов получения минимума в точке. Используемая память — $O(n \log n)$. При помощи двоичных подъемов с линейной памятью можно уменьшить потребляемую память до $O(n)$.
Упражнение: Дано подвешенное дерево. $p_v$ — предок вершины $v$ ($p_v < v$). В каждой его вершине $v$ находится какая-то линейная функция $v \cdot x + b_v$ и число $a_v$. Для каждой вершины дерева необходимо найти минимум по линейным функциям на пути до корня в точке $a_v$.
В случае, если в задаче необходим динамический CHT, то есть прямые не упорядочены монотонно по углу наклона, задача становится немного сложнее. Обычно в таком случае прямые хранятся в std::set, и при добавлении по обе стороны от добавляемой прямой удаляются ненужные. Чтобы сделать эту структуру неамортизированной, будем хранить вместо std::set декартово дерево. Тогда спуском по дереву можно найти левую и правую границы отрезка прямых, которые нужно удалить, после чего можно вставить новую прямую. Спуск по дереву в данном случае является заменой стандартному бинпоиску. Чтобы сделать эту структуру персистентной, необходимо использовать персистентное декартово дерево.
В отличие от простого алгоритма для обычного CHT, алгоритм для динамического CHT сложен в реализации, поэтому рекомендуется вместо него использовать все-таки дерево Ли Чао.