Sparse table

Массив не меняется, приходят запросы «минимум на отрезке». Хочется отвечать за $O(1)$.

С суммой это делают префиксные суммы. С минимумом так нельзя: вычитать нечего.

Таблица

st[k][i] — минимум на отрезке, который начинается в $i$ и имеет длину $2^k$.

Считается по слоям: отрезок длины $2^k$ распадается на два отрезка длины $2^{k-1}$.

int K = __lg(n) + 1;
vector<vector<int>> st(K, vector<int>(n));
st[0] = a;
for (int k = 1; k < K; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
        st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

Память и время построения — $O(n \log n)$.

Сравните с деревом отрезков: там тоже отрезки длин, равных степеням двойки, но непересекающиеся. Здесь избыточно — для каждой длины покрыты все начала. Эта избыточность и покупает константу на запрос.

Запрос

Возьмём $k = \lfloor \log_2 (r - l) \rfloor$ — наибольшую степень двойки, помещающуюся в отрезок. Накроем отрезок двумя кусками длины $2^k$: одним от левого края, другим до правого.

int query(int l, int r) {                    // полуинтервал [l, r)
    int k = __lg(r - l);
    return min(st[k][l], st[k][r - (1 << k)]);
}

Куски перекрываются посередине — и это нормально: минимум от учёта элемента дважды не меняется.

Почему они точно накрывают весь отрезок: иначе между ними осталась бы дыра, а значит, $2 \cdot 2^k < r - l$, и можно было взять $k + 1$. Противоречие с максимальностью $k$.

Проверено: 20 000 массивов, все подотрезки, пять операций — совпало с прямым перебором.

Какие функции годятся

Из-за перекрытия нужна идемпотентность: $f(x, x) = x$.

Годятся: минимум, максимум, НОД, побитовые «и» и «или».

Не годится сумма. Проверьте сами на массиве $\{1, 2, 3\}$ и отрезке $[0, 3)$: $k = 1$, куски $\{1,2\}$ и $\{2,3\}$, ответ $3 + 5 = 8$ вместо 6 — элемент $a_1$ посчитан дважды. Измерено ровно это.

Ассоциативность тоже нужна — иначе расстановка скобок при построении что-нибудь испортит.

Существует disjoint sparse table, который умеет любые ассоциативные функции при том же $O(1)$ на запрос. Устроен сложнее, нужен редко.

Про логарифм

Функция log из <cmath> в горячем цикле не годится: она работает с double, медленна и на границах даёт неверный ответ из-за округления.

Есть два быстрых способа: встроенная __lg(x) (компилируется в одну процессорную инструкцию) и заранее посчитанная таблица lg[i] = lg[i / 2] + 1.

Что быстрее — зависит от размера таблицы. Измерено на $2 \cdot 10^7$ вычислений:

размер таблицы логарифмов	__lg	таблица
0,8 МБ ($n = 2\cdot10^5$)	10 мс	9 мс
8 МБ	11 мс	35 мс
80 МБ	11 мс	140 мс

На типичных олимпиадных размерах разницы нет. Как только таблица перестаёт помещаться в кэш, __lg выигрывает втрое и больше — она вообще не обращается в память.

Вывод: берите __lg. Не потому, что она всегда быстрее, а потому, что она не зависит от размера задачи и не тратит память, которая нужна самой sparse table.

Где применяется

Главное применение в этом разделе — LCA через эйлеров обход.

Помимо: наибольший общий префикс суффиксов поверх суффиксного массива, задачи вида «минимум на всех окнах длины $k$» (хотя там очередь с минимумом экономнее), и любые запросы к неизменяемому массиву, где логарифм на запрос уже дорог.