Разреженная таблица
Разреженная таблица (Sparse Table) — это структура данных для обработки запросов на отрезке по статическому массиву (массив не изменяется).
Чаще всего используется для:
После предварительной обработки:
Любое число можно представить как сумму степеней двойки:
То же самое можно сделать с длиной отрезка.
Любой отрезок можно представить как объединение двух перекрывающихся отрезков длины :
Для идемпотентных операций (min, max, gcd) это работает идеально.
Создадим таблицу:
где:
i — начало отрезкаj — степень двойкиtable[i][j] хранит ответ на отрезке длины , начинающемся в iДля этого типа будет определено как . Таблица будет построена следующим образом:
Чтобы ответить на запрос для диапазона , нам нужно пройти через все степени двойки (начиная с самой высокой). Если , мы нашли первую часть диапазона и можем продолжить с оставшимся диапазоном .
Разреженная таблица лучше всего отвечает на такого рода запросы со сложностью . Идея заключается в том, что в отличие от запросов на сумму, минимум не требует, чтобы диапазоны не перекрывались, поэтому вместо того, чтобы разбивать на неперекрывающиеся диапазоны за , мы можем просто разбить диапазон на 2 перекрывающихся диапазона длиной в степень 2.
Например, рассмотрим диапазон . Его можно разбить на и , которые перекрываются в 7.
Чтобы ответить на запрос диапазона от до , мы находим наибольшее , такое что и возвращаем минимум из table[L][j] и table[R - 2^j + 1][j].
Предварительная обработка: , где — размер массива.
Требуется вычислить значения для всех отрезков длины .
Ответ на запрос:
Память: — хранится таблица для всех степеней двойки.
Разреженная таблица эффективна, когда:
const int MAXN = 100000;
const int LOG = 20;
int table[MAXN][LOG];
int lg[MAXN];
int f(int a, int b) {
return min(a, b); // можно заменить на max, gcd и т.д.
}
void buildSparseTable(int arr[], int N) {
// предварительно считаем логарифмы
lg[1] = 0;
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
// инициализация для длины 1
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
// динамическое построение
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = f(
table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]
);
}
}
}
void buildSparseTable(int arr[], int N) {
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = table[i][j - 1] + table[i + (1 << (j - 1))][j - 1];
}
}
}
long long sum = 0;
// 2^25 обычно достаточно в большинстве задач
for (int i = 25; i >= 0; i--) {
if ((1 << i) <= R - L + 1) {
sum += table[L][i];
L += (1 << i);
}
}
int query(int L, int R) {
int j = (int)log2(R - L + 1);
return min(table[L][j], table[R - (1 << j) + 1][j]);
}