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

[wataru]

работают в среднем за 20– 30 нс на запрос.

А какая временная сложность у предподсчета и у самих запросов? Я правильно понимаю, что там O(n log n) на предподсчет и O(log n) на запросы из-за дерева, но скорость достигается за счет SIMD и впихивания основных структур в кэш процессора?

Как оно сравнивается с O(n) предподсчетом и O(1) запросах в оффлайн алгоритме о котором я писал тут?

[malkovsky]

Нет, предподсчет линейный, разве что формально для спарс таблицы используется размер блока n/C, но это легко исправить на n/log n как. Запросы за O(log n), но вроде понятно из построения, что высота дерева очень маленькая.

20-30 нс -- это достигается в первую очередь из оптимизацией покрывающим интервалом. Вообще оптимизация довольно естественная, сам до неё дошел, но потом обнаружил в статье у поляков (но больше нигде не видел). По сути большая часть запросов получается из спарс таблицы, вот тут https://github.com/Malkovsky/pixie/blob/main/include/pixie/rmq.h есть подробные замеры, там видно, что короткие запросы не покрываются этой оптимизацией, поэтому дольше отрабатывают (у поляков в статье тот же эффект).

Как оно сравнивается с

Для замеров достаточно реализовать вот этот интерфейс