Разреженная таблица

Разреженная таблица

Разреженная таблица (англ. sparse table) — структура данных, позволяющая отвечать на запросы минимума на отрезке за \(O(1)\) с препроцессингом за \(O(n \log n)\) времени и памяти.

Разреженная таблица — это следующий двумерный массив размера \(n \times\log n\):

\[ t[i][k] = \min \{ a_i, a_{i+1}, \ldots, a_{i+2^k-1} \} \]

По-русски: считаем минимумы на каждом отрезке длины \(2^k\).

Такой массив можно посчитать за его размер, итерируясь либо по \(i\), либо по \(k\):

\[ t[i][k] = \min(t[i][k-1], t[i+2^{k-1}][k-1]) \]

Имея таком массив, мы можем для любого отрезка быстро посчитать минимум на нём. Заметим, что у любого отрезка имеется два отрезка длины степени двойки, которые пересекаются, и, главное, покрывают его и только его целиком. Значит, мы можем просто взять минимум из значений, которые соответствуют этим отрезкам.

Последняя деталь: для того, чтобы константа на запрос стала настоящей, вместо функции log нужно предпосчитать массив округленных вниз логарифмов.

int a[maxn], lg[maxn], mn[maxn][logn];

int rmq (int l, int r) {
    int t = lg[r-l+1];
    return min(mn[l][t], mn[r-(1<<t)+1][t]);
}

// Это считается уже где-то в первых строчках main:

for (int l = 1; l < logn; l++)
    for (int i = (1<<l); i < maxn; i++)
        lg[i] = l;

for (int i = n-1; i >= 0; i--) {
    mn[i][0] = a[i];
    for (int l = 0; l < logn-1; l++)
        mn[i][l+1] = min(mn[i][l], mn[i+(1<<l)][l]);
}

2d Static RMQ

Эту структуру тоже можно обобщить на большие размерности. Пусть мы хотим посчитать RMQ на подквадратах. Тогда вместо массива t[i][k] у нас будет массив t[i][j][k], в котором вместо минимума на отрезах будет храниться минимум на квадратах тех же степеней двоек. Получение минимума на произвольном квадрате тогда уже распадется на четыре минимума на квадратах длины \(2^k\).

В общем же случае от нас просят минимум тоже на прямоугольниках. Тогда делаем предподсчет, аналогичный предыдущему случаю, только теперь тут будет \(O(n \log^d n)\) памяти и времени на предподсчет.

Примечания

В отличие от дерева отрезков, разреженная таблица является статической структурой данных, то есть её нельзя дёшево обновлять (но можно достраивать на ходу — см. задачу «Антиматерия» с РОИ-2017).

Разреженную таблицу часто применяют для решения задачи о наименьшем общем предке, так как её можно свести к RMQ.

Разреженную таблицу можно применять не только для минимума или максимума. От операции требуется только ассоциативность (\(a ∘ (b ∘ c) = (a ∘ b) ∘ c\)), коммутативность (\(a ∘ b = b ∘ a\)) и идемпотентность (\(a ∘ a = a\)). Например, её можно применять для нахождения gcd.

Для больших таблиц порядок итерирования и расположение данных в памяти сильно влияет на скорость построения — это связано с работой кэшей.

Упражнение. Какой из 4 вариантов итерирования и layout-а самый эффективный? (Подсказка: не тот, который приведен в этой статье.)