- •Граф. Ориентированный граф. Представления графа. Обход графа в глубину и в ширину.
- •Топологическая сортировка. Подсчет числа путей в орграфе.
- •Сильно связные компоненты.
- •Поиск кратчайших путей в графе. Алгоритм Флойда. Алгоритм Дейкстры. Алгоритм Форда-Беллмана.
- •Алгоритм a*. Эвристики.
- •Минимальное остовное дерево. Алгоритм Прима. Биномиальная куча.
- •Амортизационная стоимость. Фибоначчиева куча. Амортизационная стоимость (анализ)
- •Метод потенциалов
- •Структура
- •Фибоначчиева Куча
- •Время работы
- •Система непересекающихся множеств. Алгоритм Крускала.
- •Наивная реализация
- •Эвристика сжатия пути
- •Эвристика объединения по рангу
- •Потоки, Форда-Фалкерсона.
- •Декартово дерево
- •Дерево Фенвика. Дерево отрезков и динамическое программирование для rmq.
- •Сведение rmq к lca и наоборот.
- •Препроцессинг
- •Ответы на запросы
- •Алгоритм
- •Доказательство
- •Сложность
- •Алгоритм
- •Минимум внутри блока
- •Результат
- •Поиск нескольких минимумов на отрезке. Задача поиска подстрок. Алгоритм Рабина-Карпа. Конечный автомат. Алгоритм Бойера-Мура.
- •Метод хеширования
- •Алгоритм
- •Время работы
- •Алгоритм Бойера-Мура
- •Поиск со звездочками. Алгоритм Кнута-Морриса-Пратта.
- •Время работы
- •Алгоритм Ахо-Корасика.
- •Дерево ключевых слов (бор)
- •Пример дерева ключевых слов (бора)
- •Построение бора
- •Поиск строки в бору
- •Автомат Ахо-Корасик
- •Суффиксное дерево, Алгоритм Укконена.
- •2. Квадратичный алгоритм
- •3. Линейный алгоритм
- •Суффиксный массив.
- •Наивный алгоритм поиска
- •Алгоритм, использующий префиксы циклических сдвигов
- •Исключения
- •Шаблоны
- •Stl: итераторы
- •Сортировка и поиск в stl. Алгоритмы stl
- •Куча в stl. Алгоритмы stl.
- •Ассоциативный массив. Интерфейс, варианты реализации.
Сведение rmq к lca и наоборот.
LCA (least common ancestor)
Задача
LCA (наименьший общий предок)
для двух вершин
и
в
корневом дереве
называется
узел
,
который среди всех узлов, являющихся
предками как узла
,
так и
,
имеет наибольшую глубину. Пусть
дано корневое дерево
.
На вход подаются запросы вида
,
для каждого запроса требуется найти их
наименьшего общего предка.
Четыре
основных алгоритма:
Самый простой, наивный алгоритм для нахождения наименьшего общего предка — вычислить глубину вершин u и v и постепенно подниматься из каждой вершины вверх по дереву, пока не будет найдена общая вершина:
Процедура LCA(u, v):
h1 := depth(u) // depth(x) = глубина вершины x
h2 := depth(v)
while h1 ≠ h2:
if h1 > h2:
u := parent(u)
h1 := h1 - 1
else:
v := parent(v)
h2 := h2 - 1
while u ≠ v:
u := parent(u) // parent(x) = непосредственный предок вершины x
v := parent(v)
return u
Время работы этого алгоритма составляет O(h), где h — высота дерева. Кроме того, может понадобиться препроцессинг, требующий O(n) времени, для нахождения непосредственного предка для всех вершин дерева и глубины вершин (но, как правило, эта структура на дереве уже имеется) – делается обходом графа.
Алгоритм за O(sqrt(H)). шаг первый: BFS – узнаем глубину дерева и глубину каждой из вершин
Шаг второй: DFS – Делим на уровни длиной sqrt(H) (их всего будет sqrt(H)). Для каждой вершины считаем d[v] = первый предок из предыдущего уровня.
Как считать? Если глубина вершины кратна sqrt(H), значит они или первая, или последняя в уровне – обрабатываем отдельно. Иначе d[v] = d[u], где u – прямой предок v. Итого предпроцессинг за O(H). Запрос:
Если вершины на разных уровнях – прыгаем из вершины с меньшим уровнем, пока уровень не будет одинаковым (максимум – O(sqrtH)). Когда достигли одного уровня, то P[v] = P[u], то LCA u,v находится между ними и вершиной P[u] = P[v]. Просто поднимаемся вверх (по прямым родителям), пока не окажемся в одной вершине. Если P[u] != P[v] – максимум за O(sqrt(H)).
Итого алгоритм работает за <O(N), O(sqrtH)>
Метод двоичного подъема Данный алгоритм является on-line (то есть сначала делается препроцессинг, затем алгоритм работает в формате запрос-ответ).
Препроцессинг
Препроцессинг
заключается в том, чтобы посчитать
функцию:
—
номер вершины, в которую мы придем если
пройдем из вершины
вверх
по подвешенному дереву
шагов,
причем если мы пришли в корень, то мы
там и останемся. Для этого сначала
обойдем дерево в глубину и для каждой
вершины запишем номер ее родителя
и
глубину вершины в подвешенном дереве
.
Если
—
корень, то
.
Тогда для функции
есть
рекуррентная формула:
Ведь
2i-1+2i-1=2i
Для
того чтобы отвечать на запросы нам нужны
будут только те значения
,
где
,
ведь при больших
значение
будет
номером корня.
Всего
состояний динамики
,
где
—
это количество вершин в дереве. Каждое
состояние считается за
.
Поэтому суммарная сложность времени и
памяти препроцессинга —
.
