Sparse Table

Материал из Algocode wiki
Версия от 16:41, 27 марта 2020; Gutrov Egor (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Алгоритм

Пусть дан массив из $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]$ (этот массив и называется Sparse Table). Мы хотим, чтобы $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, не превышающую данного числа. Точнее, нам понадобится логарифм этого числа, так как в $S$ мы используем именно их.

Сделать этот предподсчёт можно, например, следующим элегантным кодом

vector<int> logs(n + 1, 0);
logs[1] = 0;
for (int i = 1; i <= n; ++i) {
  logs[i] = logs[i / 2] + 1;
}

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

Сделав эти 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][k])$).

Заметим, что на самом деле Sparse Table можно строить не только для операции минимума, но и для многих других операций, таких что повторение одной и той же части отрезка в операции дважды не влияет на ответ. Например Sparse Table можно построить для побитового И и побитового ИЛИ, но нельзя построить для побитового XOR или для количества минимумов. Для этих операций тоже есть некий аналог Sparse Table, Disjoint Sparse Table.

Несколько измерений

Sparse Table можно построить не только для одномерного массива, но и для таблиц из нескольких измерений. Для примера рассмотрим такую задачу. Есть таблица $n \times m$, надо сделать предподсчёт за $O(n\,m \log(n) \log(m))$, после чего отвечать на запрос "минимум в прямоугольнике".

В одномерном случае мы считали минимум в отрезках с длиной, равной степени 2. Расширим эту идею и будем считать минимум в прямоугольниках, у которых длина каждой стороны это степень 2. Заметим, что посчитать минимум в прямоугольниках, у которых высота равна $1=2^0$, а длина это какая-то степень 2 мы можем так же, как мы считали Sparse Table для одномерного массива. Так же заметим, что прямоугольник, у которого высота это $2^k$ делится на 2 прямоугольника, у которых высота $2^{k - 1}$. Тогда мы можем для второго измерения всё делать так же, как и для одномерного случая.

Ответ на запрос тоже аналогичен одномерному случаю. Если надо найти минимум в прямоугольнике, с координатами от клетки $(x_1, y_1)$ до клетки $(x_2, y_2)$, то найдём максимальные $k$ и $l$, что $2^k \le x_1 - x_2 + 1$ и $2^l \le y_1 - y_2 + 1$. Тогда заметим, что если в углы начального прямоугольника поставить прямоугольники с длиной по $x$ равной $2^k$, а с длиной по $y$ равной $2^l$, то эти 4 прямоугольника полностью его покроют, но за границы не выйдут. Тогда взяв миинимум по этим 4 прямоугольникам мы ответим за запрос.

См. также

Disjoint Sparse Table



Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil