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

Разреженная таблица (англ. 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) { // полуинтервал [l; r)
    int t = lg[r-l];
    return min(mn[l][t], mn[r - (1 << t)][t]);
}


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

for (int l = 0; 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]);
}

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

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

Применения

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

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

2d Static RMQ

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

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

Ограничения на операцию

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

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

int sum(int l, int r) { // [l, r)
    int res = 0;
    for (int d = logn - 1; d >= 0; d--) {
        if (l + (1 << d) < r) {
            res += t[l][d];
            l += (1 << d);
        }
    }
    return res;
}

Это работает быстрее, чем, например, дерево отрезков, но тоже асимптотически за \(O(\log n)\), да ещё и с дополнительной памятью. Но есть способ это ускорить.

Disjoint Sparse Table

Мы хотим иметь какую-то структуру, которая может считать функцию \(f\) на отрезке, при том что \(f\) не удовлетворяет условию идемпотентности. Стандартная разреженная таблица тут не подойдёт — в ней нельзя найти \(O(1)\) непересекающихся отрезков.

Сделаем следующее: мысленно построим на массиве дерево отрезков и (уже не мысленно) для каждого его отрезка \([l, r)\) посчитаем \(f\) на всех отрезках от его центрального элемента — то есть от элемента с индексом \(m = \lfloor \frac{l + r}{2} \rfloor\) — до всех остальных элементов \(k \in [l, r)\). Для каждого элемента массива будет \(O(\log n)\) центральных, а значит суммарно на это потребуются те же \(O(n \log n)\) времени и памяти.

Утверждение. Любой запрос \([l, r)\) разбивается на \(O(1)\) непересекающихся преподсчитанных интервалов.

Доказательство. Возьмем самый высокий центральный элемент \(m\), принадлежащий запросу. Его отрезок полностью покрыает запрос — если бы это было не так, то самым высоким был бы не \(m\), а какая-то из его границ . Раз отрезок запроса \([l, r)\) полностью покрыт, и \(m\) лежит внутри него, то \([l, r)\) можно разбить на предпосчитанные \([l, m)\) и \([m, r)\).

Решать задачу мы так и будем: найдём нужный центральный элемент и сделаем два запроса от него.

Реализация

Сложная часть — найти этот центральный элемент за константное время — станет чуть проще, если мы будем работать только с массивами длины степени двойки и, соответственно, полными деревьями отрезков. Массивы неподходящей длины дополним до ближайшей степени двойки специальным нейтральным элементом, зависящим от самой операции (например, \(0\) для сложения или \(1\) для умножения).

Будем хранить всю структуру (предпосчитанные значения на отрезках) в массиве t[logn][maxn], в котором первым параметром будет уровень в дереве отрезков (число \(d\) для отрезков размера \(2^d\)), а вторым — граница соответствующего интервала (число \(k\)). Этой информации достаточно, чтобы однозначно восстановить отрезок.

Для ответа на запрос нам достаточно найти только уровень нужного центрального элемента. Чтобы научиться делать это эффективно, нам понадобится немного поразмышлять о природе дерева отрезков.

Заметим, что любая вершина \(k\)-того уровня соответствует какому-то отрезку \([l, l + 2^k)\), причём \(l\) делится на \(2^k\). Двоичное представление всех индексов на этом отрезке будет иметь какой-то общий префикс, а последние \(k\) знаков будут различными.

Нам нужно найти уровень нужного центрального элемента — это то же самое, что и уровень наименьшего общего отрезка для элементов \(l\) и \(r\). Используя предыдущий факт, получаем, что искомый уровень будет равен позиции самого значимого бита, который отличается у чисел \(l\) и \(r\). Его можно найти за константное время выражением \(h_{[l,r)]} = \lfloor \log_2 (l \oplus r) \rfloor\), если заранее предпосчитать логарифмы.

Для примера, построим DST для умножения по составному модулю:

const int maxn = (1 << logn);
int a[maxn], lg[maxn], t[logn][maxn];

const int neutral = 1;
int f(int a, int b) {
    return (a * b) % 1000;
}

void build(int l, int r, int level = logn - 1) {
    int m = (l + r) / 2;
    
    int cur = neutral;
    for (int i = m + 1; i < r; i++) {
        cur = f(cur, a[i]);
        t[level][i] = cur;
    }
    
    cur = neutral;
    for (int i = m; i >= l; i--) {
        cur = f(cur, a[i]);
        t[level][i] = cur;
    }
    
    if (r - l > 1) {
        build(l, mid, level+1);
        build(mid, r, level+1);
    }
}

int rmq(int l, int r) { // [l, r)
    int level = lg[l ^ r];
    int res = t[level][l];
    // и, если правый отрезок не пустой:
    if (r & ((1 << lg[l ^ r]) - 1)))
        res = f(res, t[level][r]);
    return res;
}

TODO: скорее всего, тут есть баги.