Sparse Table

Материал из Algocode wiki
Перейти к: навигация, поиск

Алгоритм

Пусть дан массив из $n$ чисел, и требуется с предподсчётом за $O(n \log n)$ отвечать на запрос "минимум на отрезке" за $O(1)$ в онлайне.

Предподсёт

Для этого сделаем следующий предподсчёт: в массиве для каждого подотрезка, длина которого является степенью 2, найдём минимум в нём. Таким обазом мы хотим найти минимум в отрезках $[0, 0],\ [1, 1],\ \ldots,\ [n-1, n - 1]$, $[0, 1],\ [1, 2],\ \ldots,\ [n - 2, n - 1]$, $[0, 3],\ [1, 4],\ \ldots,\ [n - 4, n - 1]$, и так далее.

Заметим, что сделать мы это можем за $O(n \log n)$. Заведём массив $S[n][\log n]$. Мы хотим, чтобы $S[i][j]$ было равно минимуму в отрезке, начиная с $i$ и имеющему длину $2^j$. Нетрудно заметить, что $S[i][0]$ равно числу, стоящему на $i$-м месте массива. Теперь научимся для фиксированного $j$ и всех возможных $i$ считать $S[i][j]$, если мы уже знаем все $S[i][j - 1]$. Как мы знаем, $S[i][j]$ этот минимум в отрезке массива, начинающегося в позиции $i$ и имеющем длину $2^j$. Такой отрезок можно разделить на 2 меньших отрезка длиной $2^{j - 1}$, начинающихся в позициях $i$ и $i + 2^{j - 1}$. Тогда если посчитан минимум в обоих таких отрезках, то мы можем найти минимум в исходном, что нам и требовалось сделать. Соответственно, так можно посчитать все $S[i][j]$.

Так же сделаем следующий предподсчёт: для всех чисел от 1 до $n$ найдём максимальную степень 2, не превышающую данного числа.

Ответ на запрос

Сделав эти 2 предподсчёта, мы готовы быстро отвечать на запросы. Пусть нам даны пары индексов $l$ и $r$, и мы хотим найти минимум на отрезке от $l$ до $r$. Длина такого отрезка равна $r - l + 1$. Для этой длины мы уже преподсчитали максимальное $k$, что $2^k \le r - l + 1$. Тогда заметим, что если мы возьмём два отрезка, длиной $2^k$, один из которых начинается в $l$, а второй заканчивается в $r$, то эти 2 отрезка будут находится полностью внутри начального отрезка, причём так как их суммарная длина больше длины нашего отрезка (по определению $k$), то они полностью покроют отрезок с $l$ по $r$ (некоторые части будут покрыты 2 раза). Тогда чтобы ответить на запрос минимума на отрезке с $l$ по $r$, надо просто взять минимум из уже посчитанных минимумов в этих двух отрезках (т.е. ответ это $min(S[l][k], S[r - 2^{k - 1} + 1][k])$).