Дерево Li Chao: различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 4: | Строка 4: | ||
====Структура дерева==== | ====Структура дерева==== | ||
− | Построим дерево, аналогичное [[ | + | Построим дерево, аналогичное [[дерево отрезков|дереву отрезков]], над всем множеством координат (если координаты вещественные, то над всем множеством с определенной точностью). В каждой вершине дерева будем хранить какую-то линейную функцию (изначально нейтральную). |
Определим $get$-запросы для координаты $x$ над деревом таким образом: | Определим $get$-запросы для координаты $x$ над деревом таким образом: | ||
Строка 20: | Строка 20: | ||
====Реализация==== | ====Реализация==== | ||
− | Очень часто данное дерево надо реализовывать в [[ | + | Очень часто данное дерево надо реализовывать в [[динамические структуры данных|неявном виде]]. |
<syntaxhighlight lang='c++' line='line'> | <syntaxhighlight lang='c++' line='line'> | ||
Строка 73: | Строка 73: | ||
{{Автор|Константин Амеличев|kik0s}} | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [[Категория:Конспект]] | ||
[[Категория:Оптимизации динамики]] | [[Категория:Оптимизации динамики]] |
Текущая версия на 13:13, 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 = \frac{l + r}{2}$ и на функцию $g$, записанную в $v$.
- Если $f(m) > g(m)$, то поменяем $f, g$ местами.
- Заметим, что теперь функция $f$ может быть максимальной либо на $[l, m - 1]$, либо на $[m + 1, r]$ (если переменные вещественные, то $m \pm \epsilon$)
- Рекурсивно решим задачу в соответствующем поддереве
Реализация
Очень часто данное дерево надо реализовывать в неявном виде.
1 struct line {
2 int k = 0, m = 0;
3 line() {}
4 line(int k, int m): k(k), m(m) {}
5 int get(int x) {
6 return k * x + m;
7 }
8 };
9
10 line t[4 * MAXN];
11
12 void upd(int v, int tl, int tr, line L) {
13 if (tl > tr) {
14 return;
15 }
16 int tm = (tl + tr) / 2;
17 bool l = L.get(tl) > t[v].get(tl);
18 bool mid = L.get(tm) > t[v].get(tm);
19 if (mid) {
20 swap(L, t[v]);
21 }
22 if (l != mid) {
23 upd(2 * v, tl, tm - 1, L);
24 }
25 else {
26 upd(2 * v + 1, tm + 1, tr, L);
27 }
28 }
29
30 int get(int v, int tl, int tr, int x) {
31 if (tl > tr) {
32 return 0;
33 }
34 int tm = (tl + tr) / 2;
35 if (x == tm) {
36 return t[v].get(x);
37 }
38 if (x < tm) {
39 return max(t[v].get(x), get(2 * v, tl, tm - 1, x));
40 }
41 else {
42 return max(t[v].get(x), get(2 * v + 1, tm + 1, tr, x));
43 }
44 }
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s