Дерево Li Chao

Дерево 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