Алгоритмы и структуры данных 14. Декомпозиция
0:00 - Вступление
1:22 - Алгоритм Фарах-Колтона и Бендера
14:04 - RMQ c предподсчетом за O(n) и ответом на запрос за O(1)
28:12 - Центроидная декомпозиция
34:10 - Задача: поиск числа пар вершин в дереве на расстоянии d
55:10 - Heavy-light декомпозиция
1:08:48 - Утверждение: путь между u и v пересекает не больше O(logN) тяжелых путей
1:12:27 - Ответ на запрос
Дата лекции 04.05.23
Лектор: Степанов И.Д.
Монтажер: Калинин Иван
Оператор: Сибиряков Михаил
