Sparse Table



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

Идея

Давайте рассматривать эту структуру на примере задачи поиска минимума на отрезке (RMQ). Для операции максимума все будет аналогично.

Идея этой структуры кроется в ее названии: разреженная таблица. Что же это за таблица, и почему она разреженная? Под таблицей здесь понимается таблица, в которой хранятся ответы на все возможные запросы поиска минимума на отрезке. То есть квадрат, в котором по вертикали отложены все возможные левые границы, а по горизонтали все возможные правые границы. Имея такую таблицу, можно без труда отвечать на запросы поиска минимума на отрезке просто обращаясь к соответствующим полям нашей таблицы. Однако чтобы построить такую таблицу, нужно потратить $O(n^2)$ времени и памяти, что абсолютно недопустимо.

В этот момент мы решаем, что хранить всю таблицу мы не будем, а будем хранить разреженную таблицу. То есть сохраним значения не для всех возможных отрезков, а только для некоторых. Однако это должны быть такие отрезки, чтобы из ответов для них можно было сконструировать ответ для любого отрезка. В обычной таблице любой отрезок уже был предпосчитан. Такого мы себе позволить не можем, но давайте сделаем немного более слабое условие: должно выполняться условие, что любой отрезок массива можно накрыть двумя предпосчитанными отрезками. Тогда минимум на отрезке — это минимум из двух минимумов на этих подотрезках. При этом эти подотрезки могут пересекаться. В этот момент как раз таки мы и воспользуемся тем, что мы ищем именно минимум на отрезке, а не сумму. Если бы мы искали сумму, то нам было бы необходимо, чтобы подотрезки, на которые мы разбиваем наш отрезок, не пересекались, иначе пересечение мы учтем дважды.

Для минимума это непринципиально: если мы возьмем дважды минимум с одним и тем же числом, то результат не поменяется. Такое свойство операций называется идемпотентностью. Другие идемпотентные операции на отрезке тоже можно считать при помощи разреженных таблиц: максимум (аналогично минимуму), НОД ($gcd(a, a) = a$, однако вычисление НОДа двух чисел занимает неконстантное время, поэтому НОД на отрезке мы будем искать все таки не за $O(1)$, а за время работы одного вызова функции $gcd$) и т.д.

Какие же отрезки нужно предпосчитать, чтобы любой отрезок запроса разбивался на два предпосчитанных отрезка, но при этом нам не нужно было предпосчитывать очень много всего? Давайте предпосчитаем минимум для всех отрезков, длины которых равны степени двойки. Сколько всего таких отрезков? Для каждой длины существует не более $n$ отрезков такой длины (при фиксированной длине у всех таких отрезков разные левые границы). При этом разных степеней двойки, не больших $n$, есть $\left\lfloor \log n \right\rfloor$ штук: $1$, $2$, $4$, $\ldots$, $2^{\left\lfloor \log n \right\rfloor}$. Так что наша структура будет занимать $O(n \log n)$ памяти.

О том, как эту структуру построить и хранить, мы поговорим позже, а пока поймем, почему теперь любой отрезок разбивается на два предпосчитанных подотрезка. Пускай длина отрезка равна $len$. Пусть $2^k$ — это максимальная степень двойки, не бóльшая $len$. Тогда давайте возьмем один подотрезок длины $2^k$, начинающийся в левой границе отрезка, а другой — заканчивающийся в правой границе. Очевидно, что они будут полностью лежать внутри отрезка, потому что $2^k \le len$, осталось понять, почему они полностью покрывают отрезок, то есть пересекаются. Действительно, если они не пересекаются, то внутри отрезка длины $len$ можно поместить два непересекающихся отрезка длины $2^k$, тогда длина отрезка не меньше, чем $2^k + 2^k = 2^{k + 1}$, но ведь мы взяли число $2^k$ так, чтобы это была максимальная степень двойки, не бóльшая $len$. Противоречие.

Построение

Теперь поговорим про то, как мы будем строить и хранить эту структуру. Хранить мы ее будем в двумерном массиве размера $\log n \times n$. Для каждой степени двойки и для каждой левой границы сохраним минимум на соответствующем отрезке. Важно обратить внимание на то, что не для любой левой границы и степени двойки существует соответствующий отрезок. К примеру, для последнего индекса массива есть отрезок только длины $1$. У этой проблемы есть два решения: первое — просто игнорировать такие отрезки, потому что они нам все равно не понадобятся, второе — если отрезок вылезает за пределы массива, обрезать его концом массива. Конечно, не делать что-то легче, чем делать, поэтому мы выберем первый вариант, потому что эти отрезки все равно не используются.

Теперь нужно понять, как быстро насчитать нашу разреженную таблицу. Заметим, что для построения можно воспользоваться идеей, похожей на идею поиска минимума на любом отрезке разбиением его на два маленьких. Действительно, любой отрезок длины $2^{k}$ — это два отрезка длины $2^{k - 1}$, поэтому нужно просто взять минимум из двух минимумов. Тогда если мы изначально определим, что минимумы на отрезках длины $1$ — это просто элементы изначального массива, а потом будем считать нашу таблицу по возрастанию степени двойки, то каждое значение можно будет посчитать за $O(1)$ по следующей формуле:

sparse[k][ind] = min(sparse[k - 1][ind], sparse[k - 1][ind + (1 << (k - 1))])

Нам нужно найти минимум на полуинтервале $[ind, ind + 2^k)$, он разбивается на два полуинтервала: $[ind, ind + 2^{k - 1})$ и $[ind + 2^{k - 1}, ind + 2^k)$. И в принципе, в этой теме, как и в почти любой другой, лучше всего думать всегда про полуинтервалы, а не про отрезки, чтобы не запутаться.

Давайте приведем полный код построения разреженной таблицы за $O(n \log n)$:

vector<vector<int>> build_sparse_table(const vector<int>& arr) {
    int n = arr.size();
    int maxpow = ceil(log2(n + 1)); // 2^{maxpow} > n
    vector<vector<int>> sparse(maxpow, vector<int>(n, 0));
    sparse[0] = arr;
    for (int k = 0; k + 1 < maxpow; k++) {
        for (int ind = 0; ind + (1 << k) < n; ind++) {
            sparse[k + 1][ind] = min(sparse[k][ind], sparse[k][ind + (1 << k)]);
        }
    }
    return sparse;
}

Здесь для удобства выбран немного иной способ подсчета: мы пересчитываем не $k$-й слой через $k-1$-й, а $k+1$-й через $k$-й.

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

ind + (1 << (k + 1)) <= n

То есть полуинтервал $[ind, ind + 2^{k + 1})$ полностью лежит в границах массива. Однако мы ослабили это условие, посчитав некоторое количество лишних значений, однако мы все равно не используем такие значения при ответе на запрос, поэтому это никак не повлияет на работу нашей структуры. Но с другой стороны здесь нам не пришлось думать и вспоминать корректное условие. Все, о чем мы беспокоимся, — это то, чтобы индексы массива, через которые мы пересчитываем, были корректны. А так как мы обращаемся к индексу $ind + 2^k$, он должен быть меньше $n$.

$maxpow$ можно выбрать любым способом, чтобы оно было строго больше $\log n$.

Замечание: Порядок циклов и размерностей в построении может очень сильно влиять на время исполнения программы из-за работы с кэшами. Предложенный вариант является оптимальным (примерно в 3-5 раз быстрее других вариантов).

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

Для ответа на запрос нам надо найти ближайшую к длине отрезка степень двойки, а потом взять минимум из двух таких подотрезков. Не рекомендуется использовать для этого функцию логарифм, потому что она работает с вещественными числами, поэтому с ней можно легко ошибиться из-за точности. Можно заранее создать массив, в котором для каждого числа от $1$ до $n$ предпосчитать двоичный логарифм. Это делается следующим несложным кодом:

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

Действительно, целая часть двоичного логарифма — это то, сколько раз число надо поделить нацело на два, чтобы оно стало единицей. Это можно посчитать как раз такой динамикой: если числу $\left\lfloor \frac{i}{2} \right\rfloor$ нужно logs[i >> 1] действий, то числу $i$ нужно на одно действие больше.

Теперь можно и в построении $maxpow$ определять как logs[n] + 1.

Когда мы посчитали логарифмы, мы готовы написать функцию поиска минимума на полуинтервале:

int find_min(int l, int r) { // [l, r)
    int power = logs[r - l];
    return min(sparse[power][l], sparse[power][r - (1 << power)]);
}

Очевидно, запрос поиска минимума работает за $O(1)$.

Один из полуинтервалов, на которые мы разбиваем, должен начинаться в левой границе, а другой должен заканчиваться в правой, поэтому его левая граница, соответственно, должна быть на $2^{power}$ назад.

Обратите внимание, что благодаря тому, что мы все считаем на полуинтервалах, у нас во всей функции нет ни одной $\pm 1$.

Кроме того, есть трюк, которым можно воспользоваться в C++, чтобы не предпосчитывать логарифмы. Конечно, функцию log2 использовать не стоит, потому что она работает с числами с плавающей точкой, однако есть способ получить двоичный логарифм в целых числах. В этом нам поможет функция __builtin_clz. builtin означает «встроенная», а clz расшифровывается как «count leading zeros», то есть количество ведущих нулей. Заметим, что количество ведущих нулей как раз таки совпадает с индексом первой единицы (в числе идет $k$ нулей, а после них стоит единица; это $k$-я позиция). А индекс старшей единицы — это как раз таки логарифм числа. Однако проблема в том, что в этом случае индекс считается с другой стороны: с самого старшего $31$ бита, а нам нужен индекс с самого младшего бита, поэтому для получения целой части двоичного логарифма числа $i$, нужно воспользоваться следующей формулой:

31 - __builtin_clz(i)

Замечание: Есть альтернатива — функция __lg(i), которая сразу возвращает целую часть логарифма, однако она есть не во всех компиляторах, поэтому будьте осторожны.

Применения

Применять разреженные таблицы можно и просто для поиска минимума на отрезке как более простую альтернативу дереву отрезков, так и в специальных случаях. К примеру, можно свести задачу о поиске наименьшего общего предка в дереве к задаче RMQ по высотам на эйлеровом обходе дерева.

Разреженные таблицы для поиска суммы на отрезке

Разреженные таблицы используют тот факт, что операция, которая считается на отрезке, идемпотентна, то есть если учесть один элемент два раза, ответ не поменяется. Однако такие операции как сумма не являются идемпотентными, поэтому из стандартных отрезков разреженных таблиц нельзя за $O(1)$ посчитать сумму на отрезке. Есть альтернативный более сложный вариант построения разреженных таблиц (Disjoint Sparse Table), который разбивает любой отрезок на два непересекающихся подотрезка.

Однако сейчас давайте поймем, как искать сумму на отрезке при помощи стандартных разреженных таблиц за $O(\log n)$. Этот алгоритм будет похож на поиск предков в дереве при помощи бинарных подъемов. Давайте начнем с подотрезка, начинающегося в левой границе отрезка запроса, длины максимальной степени двойки и будем уменьшать степень, пока текущий подотрезок не попадет полностью внутрь отрезка запроса. После чего прибавим сумму на этом подотрезке к ответу и передвинем левую границу в конец этого подотрезка. Далее продолжим перебирать степени двойки по убыванию. Заметим, что если нам не подошла какая-то степень двойки, то далее она никогда нам не сможет подойти, потому что длина оставшегося отрезка запроса не увеличивается. Более того, набор взятых степеней двоек вовсе строго убывает. Действительно, если бы мы дважды взяли подотрезки длины $2^k$, вместо этого можно было бы взять один подотрезок длины $2^{k + 1}$, но мы этого почему-то не сделали. Так что весь отрезок запроса разобьется на набор непересекающихся подотрезков различных длин. Всего таких подотрезков будет не больше логарифма, потому что всего разных степеней двоек есть логарифм.

Замечание: Если начинать поиск не с самой большой степени двойки, а с самой большой степени двойки, которая не больше длины отрезка (power из поиска минимума на отрезке), то асимптотика ответа на запрос будет $O(\log len)$, где $len$ — длина отрезка запроса, что, конечно, в общем случае то же самое, что и $O(\log n)$.

long long find_sum(int l, int r) { // [l, r)
    long long ans = 0;
    for (int power = logs[r - l]; power >= 0; power--) {
        if (l + (1 << power) <= r) {
            ans += sparse[power][l];
            l += (1 << power);
        }
    }
    return ans;
}

Многомерные разреженные таблицы

Большим плюсом разреженных таблиц является простота их применения в многомерных случаях. Для примера рассмотрим двумерный случай, для б'{о}льших размерностей все будет аналогично.

Если раньше отрезок длины $n$ мы покрывали двумя подотрезками длины $2^k$, где $2^k$ — ближайшая к $n$ степень двойки, то теперь прямоугольник размера $n \times m$ мы накроем четырьмя подпрямоугольниками размера $2^k \times 2^l$ (ближайшие степени двойки к $n$ и $m$ соответственно), расположенными в углах прямоугольника запроса. То есть мы накрываем вертикальный отрезок длины $n$ двумя подотрезками длины $2^k$, накрываем горизонтальный отрезок длины $m$ двумя подотрезками длины $2^l$, и берем прямоугольники, полученные из всевозможных пар вертикальных и горизонтальных отрезков.

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

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

Очевидно, построение такой структуры будет занимать $O(n \cdot m \cdot \log n \cdot \log m)$ времени, а ответ на запрос все еще будет работать за $O(1)$.

С реализацией можно ознакомиться по ссылке.

Задачи для практики

  • Задача на поиск максимума и индекса этого максимума на отрезке.

  • Задачу E этого контеста сложно решить чем-то кроме разреженных таблиц.

  • Задачи на Disjoint Sparse Table можно прорешать в специально подготовленном контесте на codeforces.