Когда требуется выполнять запросы минимума/максимума на отрезке иногда бывает недостаточно скорости структур вроде ДО. В этом случае спасают Sparse Table (англ. разреженная таблица), обеспечивающие \(O(1)\) на запрос.
Основная идея - давайте сделаем структуру, которая может делать запросы на промежутках вида \([l;l+2^i)\).
Всего \(i\) может быть не более \( \log{n} \), следовательно структура будет занимать не более \(O(n\log{n})\) памяти.
Утверждается, что сделав всего два запроса можно узнать минимум/максимум на произвольном отрезке \([l;r]\).
Давайте найдем максимальное \(k\) такое, что \(2^k \le r-l+1\). Тогда совершим два запроса: \([l; l+2^k)\) и \( (r-2^k;r] \). То есть мы взяли первые \(2^k\) элементов и последние \(2^k\) элементов.
После, в зависимости от того, что мы хотим найти, мы берем максимум или минимум с этих двух запросов.
Почему это корректно? Во-первых, т.к. \(2^k \le r-l+1 \), отрезки наших запросов полностью лежат внутри \([l;r]\). Во-вторых, эти два отрезка пересекают друг друга, так как если они не пересекаются, значит \(2^k + 2^k < r-l+1\), следовательно \( 2^{k+1} < r-l+1\), а это значит что мы подобрали не максимальное \(k\).
Автор находит в реализации Sparse Table наиболее интересным нахождение подходящего \(k\). Можно использовать функцию встроенную в GCC __lg() либо самому написать наипростейший код вроде этого:
int len = r - l + 1; // длина подотрезка
int k = 0;
while( (1 << k) < len )
k++;
k--;
// k == __lg(len)
Но тогда асимптотика возрастет до \( O(n \log{n}) \), хотя этот логарифм на порядок быстрее чем тот же логарифм дерева отрезков.
Тем не менее можно использовать функцию __builtin_clz, возвращающая количество нулей в битовом представлении числа до первой единицы. Вычтя это значение из длины в битах нашего числа можно получить как раз-таки логарифм числа (__lg реализовано как раз с помощью __builtin_clz).
Подытоживая напишем весь код:
#define MAXN 200000
int rmq[20][MAXN]; //логарифм MAXN не превосходит 20
rmq[0] = a;
// при длине 1 запрашиваемого отрезка, исходный массив и есть "первый уровень"
for(int i=1; i < 20 ;i++)
for(int j=0;j + (1 << i) - 1 < MAXN; j++)
rmq[i][j] = min( rmq[i-1][j], rmq[i-1][j + (1 << (i-1))] );
int get_min(int l, int r) {
int k = __lg(r-l+1);
return min( rmq[k][l], rmq[k][r - (1 << k) + 1] );
}
Как несложно заметить, когда мы считаем ответ в Sparse Table мы часто пересекаем два отрезка и берем с них ответ. Для минимума/максимума это некритично, так как \( min(x,y) = min(x, min(x,y) \). Для любой функции, для которой это выполняется (свойство идемпотентности), можно использовать Sparse Table.
Для суммы такой метод, к сожалению, не прокатит. Необходимо модифицировать наш Sparse Table, чтобы делать ответ получался из непересекающихся подотрезках.
Давайте рассмотрим массив \(a\) длины \(n\), и поставим задачу нахождение суммы за \(O(1)\).
Сперва дополним массив нулями, чтобы его длина была степенью двойки (нуль никогда не изменит ответ).
Теперь рассмотрим соответствующее ДО массиву, выписав в каждой вершине все элементы, которые лежат в этой вершине. Вершины пронумеруем как в обычном ДО: если дана вершина \(v\), то левый сын имеет номер \(v*2\), а правый - \(v*2+1\).
Рассмотрим произвольный отрезок запроса \([l;r]\). Найдем вершину, которая полностью содержит данный отрезок. Рассмотрим сыновей этой вершины. Некоторый суффикс левого сына принадлежит отрезку и некоторый префикс правого сына принадлежит отрезку (возможно нулевой длины).
Тогда для каждой вершины насчитаем либо суффиксные суммы, либо префиксные суммы, если это левый сын или правый сын предка соответственно.
Теперь найдем что-то вроде LCA \(l\) и \(r\) - первая вершины снизу, хранящая отрезок, содержащий полностью отрезок \([l;r]\). На ее детях и найдем ответ.
Таким образом, осталась последняя задача: оптимально найти эту вершину. Заметим, что в двоичной системе исчисления номер этой вершины равен наибольшому общему префиксу двоичной записи чисел \(l\) и \(r\).
То есть надо найти после какого бита у нас перестает совпадать \(l\) и \(r\) и сдвинуть вправо, чтобы этот бит (и последующие) уничтожился. Это можно найти с помощью исключающего или (самый старший единичный бит).