Лекция 7. Алгоритм Фараха-Колтона и Бендера

Андрей Гейн: На этот раз мы откроем потрясающий алгоритм Фараха-Колтона и Бендера, позволяющий очень быстро решать задачи RMQ и LCA. Сначала мы внимательно разберёмся, что это за задачи такие, что ради них придумали отдельные аббревиатуры. Субъективная сложность лекции — четыре теты из пяти. Содержание: 1:35 Задача static online RMQ (range minimum query, запрос минимума на подотрезке) 4:43 Тривиальные решения задачи RMQ 8:15 Решение RMQ с помощью разреженной таблицы (sparse table) 13:07 Решение RMQ с помощ