Дерево Li Chao: различия между версиями

Версия 08:16, 27 сентября 2019

Дерево Li Chao --- это структура данных, умеющая обрабатывать два вида запросов:

Добавить линейную функцию $f(x) = ax + b$ в множество $X$.
Найти минимальное значение $f(x)$ по всем $f \in X$ при заданном $x$.

Структура дерева

Построим дерево, аналогичное дерево отрезков, над всем множеством координат (если координаты вещественные, то над всем множеством с определенной точностью). В каждой вершине дерева будем хранить какую-то линейную функцию (изначально нейтральную).

Определим $get$-запросы для координаты $x$ над деревом таким образом:

Сделаем спуск по дереву к листу, соответствующему координате $x$
Выпишем все посещенные вершины
Возьмем минимум среди всех этих функций

Теперь придумаем такие $add$-запросы, что после их выполнения $get$ корректен:

Пусть мы хотим добавить функцию $f$
Рассмотрим вершину $v$ такую, что вне отрезка $[l, r], соответствующему вершине $v$, $f$ никогда не бывает минимальной. * Посмотрим на среднюю точку для этого отрезка $m = \floor{l + r}{2}$ и на функцию $g$, записанную в $v$. * Если $f(m) < g(m)$, то поменяем $f, g$ местами. * Заметим, что теперь прямая $f$ может быть минимальной <b>либо</b> на $[l, m - 1]$, <b>либо</b> на $[m + 1, r]$ (если переменные вещественные, то $m \pm \epsilon$)
Рекурсивно решим задачу в соответствующем поддереве

Реализация

//TODO

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s

@@ Строка 3: / Строка 3: @@
 * Найти минимальное значение $f(x)$ по всем $f \in X$ при заданном $x$.
-====add====
+====Структура дерева====
-// TODO
+Построим дерево, аналогичное [[дереву отрезков|дерево отрезков]], над всем множеством координат (если координаты вещественные, то над всем множеством с определенной точностью). В каждой вершине дерева будем хранить какую-то линейную функцию (изначально нейтральную).
-====get====
+Определим $get$-запросы для координаты $x$ над деревом таким образом:
-// TODO
+* Сделаем спуск по дереву к листу, соответствующему координате $x$
+* Выпишем все посещенные вершины
+* Возьмем минимум среди всех этих функций
+Теперь придумаем такие $add$-запросы, что после их выполнения $get$ корректен:
+* Пусть мы хотим добавить функцию $f$
+* Рассмотрим вершину $v$ такую, что <i>вне отрезка</i> $[l, r], соответствующему вершине $v$, $f$ никогда не бывает минимальной.
+* Посмотрим на среднюю точку для этого отрезка $m = \floor{l + r}{2}$ и на функцию $g$, записанную в $v$.
+* Если $f(m) < g(m)$, то поменяем $f, g$ местами.
+* Заметим, что теперь прямая $f$ может быть минимальной <b>либо</b> на $[l, m - 1]$, <b>либо</b> на $[m + 1, r]$ (если переменные вещественные, то $m \pm \epsilon$)
+* Рекурсивно решим задачу в соответствующем поддереве
 ====Реализация====
 //TODO
+{{Автор|Константин Амеличев|kik0s}}
+[[Категория:Оптимизации динамики]]