Решение с помощью Эйлерова обхода: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Выпишем эйлеров обход дерева (3 вариант - выписывая вершину каждый раз, как мы в нее попад...») |
Глеб (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 8: | Строка 8: | ||
1)[[Sparse Table]] | 1)[[Sparse Table]] | ||
− | 2)[[Корневая]] | + | |
− | 3)[[Дерево | + | 2)[[Корневая декомпозиция]] |
+ | |||
+ | 3)[[Дерево отрезков]] | ||
+ | |||
+ | На практике чаще всего используется 1 способ, так как он отвечает за $O(1)$ на запрос минимума на отрезке | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 10:33, 27 ноября 2019
Выпишем эйлеров обход дерева (3 вариант - выписывая вершину каждый раз, как мы в нее попадаем). Заметим, что из всех вершин на отрезке от вершины $u$ до вершины $v$ наименьшее расстояние от корня будет иметь $lca(u, v)$, Докажем :
1) $lca(u, v)$ входит в отрезок, так как она содержится на пути между ними. 2) Весь отрезок содержится в поддереве $lca(u, v)$, так как мы не могли выйти из нее
Будем считать, что $tout_{u} <= tin_{v}$, если это не так свапнем вершины. Тогда давайте выпишем не только эйлеров обход, но и массив глубин вершин эйлерова обхода, тогда давайте найдем минимальное число на отрезке от $tout_{u}$ до $tin_{v}$, тогда вершина, которая соответствует минимуму на отрезке - $lca(u, v)$, Искать минимум на отрезке можно с помощью следующих структур
На практике чаще всего используется 1 способ, так как он отвечает за $O(1)$ на запрос минимума на отрезке
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin