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

Я собрал несколько практических наработок и сделал из них два очень компактных и быстрых варианта:
вариант с  дополнительных бит, которому иногда нужно обращаться к исходному массиву;
вариант с  дополнительных бит, который отвечает на запросы без доступа к исходному массиву.
Обе реализации очень быстры на практике: на случайных запросах по массиву размера  элементов они работают в среднем за – нс на запрос.
Для ориентира: туториал Codeforces по блочному RMQ описывает структуру, которая работает  нс на запрос для массивов длины  с 32-битными целыми числами, при этом используя  дополнительных бит.

https://habr.com/ru/articles/1055008/

Алгоритмы и Структуры данных