Дерево Ли Чао
Мотивация
Convex Hull Trick (CHT) позволяет отвечать на запросы поиска минимума (или максимума) набора линейных функций. Однако его проблемой является то, что добавляемые прямые должны быть монотонно упорядочены по углу наклона. Не всегда в задачах это выполнено. Конечно, CHT можно реализовать на двоичном дереве (std::set, к примеру) вместо стека, и в таком случае можно вставлять в произвольное место, удаляя устаревших соседей по обе стороны, однако это далеко не самый приятный алгоритм. Также, в силу того, что в CHT поддерживается стек, алгоритм амортизированный, так что какая-то одна операция добавления новой прямой может выкинуть из стека почти все старые прямые и будет работать за линейное время. Тогда если нам нужен персистентный Convex Hull Trick, мы этого сделать не сможем (есть способ сделать Convex Hull Trick неамортизированным и персистентным при помощи бинарных подъемов по стеку, либо спуска по декартову дереву в случае реализации с двоичным деревом поиска, прочитать можно здесь).
Чтобы побороть описанные выше две проблемы, нам может как раз помочь дерево Ли Чао. Это очень простая в реализации структура данных, которой не нужно, чтобы прямые были упорядочены по углу наклона. Кроме того, эта структура основана на обычном дереве отрезков, поэтому все операции будут работать за неамортизированное время, и это дерево можно делать персистентным, как и любое другое дерево отрезков.
Также, этой структуре не нужно уметь пересекать прямые, а только находить значение в точке, и ее можно использовать для произвольных функций, таких что любые две из них пересекаются не более, чем в одной точке. Помимо этого мы научимся производить массовые операции, так как мы имеем дело с деревом отрезков.
Идея
Будем решать задачу, в которой есть изначально пустое множество линейных функций $L$ и поступают запросы двух видов:
- Добавить линейную функцию $f$ в множество $L$.
- Для данного $x$ найти минимум $f(x)$ по всем функциям $f$ из $L$.
Давайте построим дерево отрезков на $x$ координатах. Обозначим максимальное значение $x$ по модулю, которое нас интересует, за $C$. Тогда время обработки одного запроса к структуре будет равно $O(\log C)$. Так как $C$ может быть очень большим числом, часто бывает ситуация, в которой дерево отрезков будет неявным. Если точки $x$ бывают вещественные, можно сделать спуск в дереве до нужной точности. Тогда если все считается с точностью до $\varepsilon$, то асимптотика будет $O(\log (C \cdot \varepsilon^{-1}))$ на запрос.
Будем в каждой вершине дерева отрезков хранить одну линейную функцию (изначально в каждой вершине хранится фиктивная функция $f(x) = +\infty$), а минимум в точке будет вычисляться как минимум по всем прямым, хранящимся в предках листа, отвечающего за эту точку.
Осталось понять, как обрабатывать запрос добавления новой прямой. Мы хотим добавить эту прямую в некоторую вершину дерева и переместить другие значения в дереве так, чтобы условие на то, что оптимальная прямая для каждой точки лежит на пути от этой точки до корня, не испортилось. Мы бы хотели положить новую прямую в корень, чтобы она лежала на пути до корня от любого листа, однако в корне, вероятно, уже лежит какая-то прямая, а мы не можем хранить сразу две прямые в вершине. Поэтому нам придется как-то решать этот конфликт.
Пускай текущая вершина отвечает за полуинтервал $[L, R)$, и у нас есть две конфликтующие функции $f$ и $g$. Если одна из них меньше другой на всем полуинтервале, то нет смысла хранить бóльшую функцию, поэтому мы можем оставить в текущей вершине меньшую и завершиться. Это можно проверить, сравнив относительный порядок значений функций $f$ и $g$ в точках $L$ и $R$. Если в точке $L$ одна была больше другой, а в точке $R$ порядок поменялся, то между этими точками точно произошло пересечение.
Замечание: Ровно в этот момент мы пользуемся тем, что любые две функции должны пересекаться не более, чем в одной точке, потому что если функции пересекаются в двух точках, то они могли не изменить свой относительный порядок даже если пересекались на этом полуинтервале.
Пусть $M$ — середина полуинтервала $[L, R)$, тогда посмотрим, в какой половине пересекаются функции. Если они пересекаются в левой половине ($[L, M)$), то в правой половине ($[M, R)$) одна из функций меньше другой во всех точках. Пусть функция $f$ меньше $g$ на правой половине. Тогда функция $g$ точно не будет минимумом для точек из правой половины. Оставим функцию $f$ в текущей вершине и протолкнем функцию $g$ дальше в левого сына. Там опять может возникнуть конфликт, который мы будем решать аналогичным образом. В случае, если функции $f$ и $g$ пересекаются в правой половине, рассуждение симметрично: одна из функций точно не будет наименьшей для точек в левой половине, поэтому мы можем оставить меньшую функцию в текущей вершине и рекурсивно попытаться протолкнуть оставшуюся прямую в правое поддерево.
Можно заметить, что на самом деле прямая, которая остается в текущей вершине — это всегда прямая с меньшим значением в точке $M$. И точку $R$ можно даже не подставлять в уравнения прямых. Просто если относительный порядок на прямых в точке $L$ такой же, как в $M$, то в правое поддерево проталкивается прямая с бóльшим значением в точке $M$, а если относительный порядок разный, то эта прямая проталкивается в левое поддерево.
Можно смотреть на это иначе: в вершине дерева отрезков находится та прямая из множества, которая имеет минимальное значение в точке $M$ из всех прямых, а оставшиеся прямые разделены по двум частям в зависимости от того, в какой из двух половин они могут быть меньше той прямой, которая хранится в текущей вершине.
Таким образом, мы будем постепенно спускаться по дереву, каждый раз запускаясь в то поддерево, в котором пересекаются конфликтующие прямые (если они не пересекаются вовсе, то мы все равно запустимся в какое-то поддерево, и в этом нет ничего страшного). Когда мы дойдем до листа, мы просто выберем меньшую функцию в этой точке и завершимся. Очевидно, что такой линейный спуск по дереву отрезков будет работать за $O(\log C)$.
С кодом можно ознакомиться по ссылке.
Замечание: Обратите внимание на то, что мы действительно нигде не пользовались тем, что мы работаем именно с линейными функциями, и мы их нигде не пересекали. Все, что нам было нужно, — считать значения функций в концах и середине отрезка текущей вершины, чтобы узнавать их относительный порядок. Таким образом, можно использовать эту структуру, к примеру, для набора кубических функций вида $k x^3 + b$, потому что любые две такие функции пересекаются не более, чем в одной точке.
Удаление прямых
Чтобы поддерживать не только добавление прямых в множество, но и удаление, можно воспользоваться идеей из задачи dynamic connectivity offline (подробнее можно прочитать здесь).
Если необходимо поддерживать структуру в online режиме, то подойдет корневая декомпозиция. Можно хранить прямые в множествах, каждое из которых имеет размер не больше $K$. Чтобы найти минимум, нужно перебрать все множества и запросить минимум в каждом из них. А для удаления прямой нужно перестроить с нуля всю структуру множества, из которого эта прямая удаляется. При оптимально подобранной константе $K$ такое решение будет работать за $O \left(n \sqrt{n \log n}\right)$
Кусочно-линейные функции
На самом деле явно видно, что наша структура не использует дерево отрезков по полной. Мы всегда и в запросе update, и в запросе get запускаемся только в одно из поддеревьев. Давайте поймем, что дерево отрезков позволяет нам расширить спектр операций, которые может поддерживать наша структура.
Действительно, обычный запрос update в дереве отрезков применяет какую-то операцию к отрезку точек, однако мы добавляем новую прямую, которая действует сразу на все точки. Давайте научимся применять добавляемую прямую только к отрезку точек, то есть добавлять в множество не прямую, а какой-то отрезок:
Действительно, обычное дерево отрезков разбивает отрезок запроса на логарифм подотрезков. Тогда давайте запустим обычный запрос изменения к дереву отрезков, а в тот момент, когда отрезок текущей вершины лежит строго внутри отрезка запроса, мы запустим из этой вершины наше старое добавление прямой в множество, которое мы раньше запускали из корня. Таким образом, мы для каждой из логарифма вершин, в которых останавливается обычный запрос изменения для дерева отрезков, запустим нашу процедуру, работающую $O(\log C)$, и итоговая асимптотика будет $O(\log^2 C)$.
Так мы, к примеру, научились находить минимум набора кусочно-линейных функций, потому что любую кусочно-линейную функцию можно разбить на линейные отрезки и добавить их в наше множество по отдельности.
С кодом можно ознакомиться по ссылке.
Ленивые обновления
Можно пойти еще дальше и добавить новые операции к поддерживаемой структуре. Для начала давайте переформулируем решаемую задачу на языке массивов.
Пусть у нас есть массив $A$ ($A_i$ — это минимум значений наших линейных функций в точке $i$). Изначально все его элементы равны $+\infty$. Кроме того есть запросы трех видов:
- Вставить (Немного странное слово, скорее это «добавить прямую на полуинтервале», но мы не будем использовать это слово из-за его схожести со словом «прибавить») линейную функцию на полуинтервале, то есть для данных $l$, $r$, $a$, $b$ присвоить $A_i = \min(A_i, a \cdot i + b)$ для всех $i$ на полуинтервале от $l$ до $r$.
- Прибавить линейную функцию на полуинтервале, то есть для данных $l$, $r$, $a$, $b$ прибавить $a \cdot i + b$ к $A_i$ для всех $i$ на полуинтервале от $l$ до $r$.
- Поиск оптимальной прямой в точке, то есть для данного $i$ вывести $A_i$.
Комбинация первого и третьего запроса — это ровно та задача, которую мы решали раньше. Однако теперь мы можем еще менять старые прямые с помощью второй операции. При этом обратите внимание, что после второй операции «прямые» перестают быть «прямыми», потому что мы прибавляем линейную функцию к другой линейной функции, но только на отрезке, а не на всей области определения. Что же нам делать, ведь для прямых, хранящихся в некоторых вершинах дерева отрезков для некоторых точек на этом отрезке эта прямая изменится, а для других — нет.
Чтобы решить эту проблему, давайте введем операцию очищения вершины. Если в данный момент в какой-то вершине дерева хранится какая-то прямая, но она нам мешает, мы можем запустить операцию вставки этой прямой для левого и правого поддерева текущей вершины, после чего данную прямую можно будет удалить из текущей вершины. Такой процесс займет $O(\log C)$ времени.
Кроме того, будем в каждой вершине дерева хранить ленивое обновление: какую линейную функцию нужно добавить ко всем прямым на этом отрезке. Тогда операция первого типа будет работать так же, как и раньше, только перед рекурсивным запуском нужно протолкнуть ленивое обновление в детей. А операция прибавления прямой на отрезке сначала очищает все вершины, которые посетила бы стандартная операция обновления в дереве отрезков (чтобы у нас не было проблем с тем, что прямая перестает быть прямой из-за того, что к одним точкам мы прибавили значение, а к другим — нет), а затем просто оставляет ленивое обновление в логарифме вершин, на которые разбивается отрезок запроса. Такая операция работает за $O(\log^2 C)$, потому что производит очистку логарифма вершин дерева, и каждая очистка занимает $O(\log C)$ времени.
Операция третьего типа просто проталкивает ленивые обновления на пути и работает как и раньше за $O(\log C)$.
Такое модифицированное дерево Ли Чао является очень функциональным инструментом для работы с линейными функциями, и многие идейные задачи можно решить просто явным применением этой структуры. Операции можно модифицировать в зависимости от задачи. К примеру, если прибавлять на отрезке не линейную функцию, а константу, можно поддерживать не только минимум значений прямых в точке, но и на целом отрезке.
С кодом можно ознакомиться по ссылке.
Задачи для практики
Далее представлены задачи, в которых можно применить продвинутые вариации дерева Ли Чао.