Паросочетание

1. Рандомизированный алгоритм поиска паросочетания в произвольном графе

Структуры данных

1. Замыкание идеи "Sparse Table" [O(n), O(log^*n)]
2. Сведение RMQ к LCA (построение декартового дерева за O(n)).
3. Offline решение RMQ за O(n)
4. Минимум на отрезке фиксированной длины за O(1).
5. Минимум на движущемся вправо отрезке произвольной длины за O(n+k).
6. Неменяющееся дерево. Функции на путях.
1. Обход дерева dfs-ом. Offline функция на пути дерева = запрос на отрезке в дереве отрезков.
2. Обобщение Sparse Table: O(K + NlogN)
3. Offline Минимум: сжатие путей: O(KlogN)
4. Online Минимум = LCA + "двоичные подъемы"
7. СНМ
1. Реализация за O(NlogN + K)
2. Реализация за O(α)
1. Док-во того, что сжатие путей = O(logN)
2. Док-во того, что подвешивание меньшего к большему дает глубину O(logN)
3. Док-во того, что обе эвристики работаею за O(log^*)