#sparse_table — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #sparse_table, aggregated by home.social.
-
Быстрые и компактные структуры данных для RMQ
Range minimum query – это классическая задача, в этой заметке решаем статический вариант. Есть массив ; нужно построить структуру данных, которая умеет быстро находить минимум и его позицию на произвольном интервале . Я собрал несколько практических наработок и сделал из них два очень компактных и быстрых варианта: вариант с дополнительных бит, которому иногда нужно обращаться к исходному массиву; вариант с дополнительных бит, который отвечает на запросы без доступа к исходному массиву. Обе реализации очень быстры на практике: на случайных запросах по массиву размера элементов они работают в среднем за 20–30 нс на запрос. Для ориентира: туториал Codeforces по блочному RMQ описывает структуру, которая отрабатывает запрос за 100 нс для массивов длины с 32-битными целыми числами, при этом используя дополнительных бит.