Дерево Li Chao: различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
| Строка 1: | Строка 1: | ||
Дерево Li Chao --- это структура данных, умеющая обрабатывать два вида запросов: | Дерево Li Chao --- это структура данных, умеющая обрабатывать два вида запросов: | ||
* Добавить линейную функцию $f(x) = ax + b$ в множество $X$. | * Добавить линейную функцию $f(x) = ax + b$ в множество $X$. | ||
| − | * Найти | + | * Найти максимальное значение $f(x)$ по всем $f \in X$ при заданном $x$. |
====Структура дерева==== | ====Структура дерева==== | ||
| Строка 9: | Строка 9: | ||
* Сделаем спуск по дереву к листу, соответствующему координате $x$ | * Сделаем спуск по дереву к листу, соответствующему координате $x$ | ||
* Выпишем все посещенные вершины | * Выпишем все посещенные вершины | ||
| − | * Возьмем | + | * Возьмем максимум среди всех этих функций |
Теперь придумаем такие $add$-запросы, что после их выполнения $get$ корректен: | Теперь придумаем такие $add$-запросы, что после их выполнения $get$ корректен: | ||
* Пусть мы хотим добавить функцию $f$ | * Пусть мы хотим добавить функцию $f$ | ||
| − | * Рассмотрим вершину $v$ такую, что <i>вне отрезка</i> $[l, r]$, соответствующему вершине $v$, $f$ никогда не бывает | + | * Рассмотрим вершину $v$ такую, что <i>вне отрезка</i> $[l, r]$, соответствующему вершине $v$, $f$ никогда не бывает максимальной. |
* Посмотрим на среднюю точку для этого отрезка $m = \frac{l + r}{2}$ и на функцию $g$, записанную в $v$. | * Посмотрим на среднюю точку для этого отрезка $m = \frac{l + r}{2}$ и на функцию $g$, записанную в $v$. | ||
| − | * Если $f(m) | + | * Если $f(m) > g(m)$, то поменяем $f, g$ местами. |
| − | * Заметим, что теперь | + | * Заметим, что теперь функция $f$ может быть максимальной <b>либо</b> на $[l, m - 1]$, <b>либо</b> на $[m + 1, r]$ (если переменные вещественные, то $m \pm \epsilon$) |
* Рекурсивно решим задачу в соответствующем поддереве | * Рекурсивно решим задачу в соответствующем поддереве | ||
====Реализация==== | ====Реализация==== | ||
| − | // | + | Очень часто данное дерево надо реализовывать в [[неявном виде|динамические структуры данных]]. |
| + | |||
| + | <syntaxhighlight lang='c++' line='line'> | ||
| + | |||
| + | struct line { | ||
| + | int k = 0, m = 0; | ||
| + | line() {} | ||
| + | line(int k, int m): k(k), m(m) {} | ||
| + | int get(int x) { | ||
| + | return k * x + m; | ||
| + | } | ||
| + | }; | ||
| + | |||
| + | line t[4 * MAXN]; | ||
| + | |||
| + | void upd(int v, int tl, int tr, line L) { | ||
| + | if (tl > tr) { | ||
| + | return; | ||
| + | } | ||
| + | int tm = (tl + tr) / 2; | ||
| + | bool l = L.get(tl) > t[v].get(tl); | ||
| + | bool mid = L.get(tm) > t[v].get(tm); | ||
| + | if (mid) { | ||
| + | swap(L, t[v]); | ||
| + | } | ||
| + | if (l != mid) { | ||
| + | upd(2 * v, tl, tm - 1, L); | ||
| + | } | ||
| + | else { | ||
| + | upd(2 * v + 1, tm + 1, tr, L); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int get(int v, int tl, int tr, int x) { | ||
| + | if (tl > tr) { | ||
| + | return 0; | ||
| + | } | ||
| + | int tm = (tl + tr) / 2; | ||
| + | if (x == tm) { | ||
| + | return t[v].get(x); | ||
| + | } | ||
| + | if (x < tm) { | ||
| + | return max(t[v].get(x), get(2 * v, tl, tm - 1, x)); | ||
| + | } | ||
| + | else { | ||
| + | return max(t[v].get(x), get(2 * v + 1, tm + 1, tr, x)); | ||
| + | } | ||
| + | } | ||
| + | </syntaxhighlight> | ||
| + | |||
{{Автор|Константин Амеличев|kik0s}} | {{Автор|Константин Амеличев|kik0s}} | ||
[[Категория:Оптимизации динамики]] | [[Категория:Оптимизации динамики]] | ||
Версия 08:34, 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