Быстрые и компактные структуры для RMQ

Range minimum query — это довольно известная академическая задача, она важна и на практике, но не сама по себе, часто она используется как рутина в алгоритмах типа LZ, суффиксных деревьев или поисковых индексов. У задачи есть несколько вариаций, основная суть в том, что есть массив чисел, нужно на произвольном подотрезке искать минимум. Самый простой пример того, как такая задача может возникнуть — запрос к базе данных в духе "какая максимальная зарплата сотрудников в возрасте от 30 до 40 лет?". На семинаре расскажу про эффективное решение статической задачи, т.е. когда массив известен заранее и не изменяется, но запросы неизвестны. Наиболее эффективное решение такой вариации — это разреженные таблицы, их проблема в том, что они требуют $O(n \log n)$ памяти и, соответственно, применимы для размеров максимум $\thicksim 10^7$. Существует много подходов, как за счёт чуть более медленных запросов сделать $O(n)$ память, включая классический алгоритм Фараха-Колтона — Бендера. Существуют также succinct подходы, которые требуют $\thicksim 2.5n$ бит памяти, но времена запросов на практике уже заметно хуже.

На семинаре расскажу, как взять лучшее из обоих миров: два варианта, каждый из которых сравним по временам запросов с разреженной таблицей, но при этом

• Первый вариант требует $1.05n$ дополнительных бит, но при этом нужно иногда подглядывать в исходный массив;
• Второй вариант требует $2.1n$ дополнительных бит, но заглядывать в исходный массив не нужно.