Задача о наименьшем общем предке в дереве (LCA)
- Определение, примеры
- Offline - версия задачи, алгоритм Ахо-Хопкрофта-Ульмана-Тарьяна, O(n)
- Online - версия задачи, сведение к +/-1RMQ, (n, log n)
- Метод Sprace Table, (n log n, 1)
- Алгоритм четырех русских перемножения булевых мартиц, O(n3/log n)
- Использование идеи четырех русских в задаче LCA для получения оценки (n, 1)
(алгоритм Фараха-Колтона - Бендера)
- Построение декартова дерева за O(n)
- Решение статической задачи RMQ за (n, 1) сведением к задаче LCA
3.14 Система непересекающихся множеств