Disjoint Sparse Table

Disjoint Sparse Table является сильно более продвинутой версией обычного Sparse Table. Как известно, обычный Sparse Table не мог быть построен для тех функций от подотрезка массива, для которых каждое число подотрезка должно быть учтено ровно один раз. Disjoint Sparse Table решает эту проблему и с предподсчётом за $O(n \log n)$ позволяет в онлайне за $O(1)$ находить почти любые функции от подотрезка, например кол-во минимумов, или произведение по непростому модулю.

Алгоритм

Рассмотрим Disjoint Sparse Table на примере следующей задачи: пусть дан массив из $n$ чисел, и требуется с предподсчётом за $O(n \log n)$ отвечать на запрос "количество минимумов на отрезке" за $O(1)$ в онлайне.

Предподсчёт

Предподсчёт будет являться разновидностью идеи «разделяй и влавствуй».

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

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

Заметим, что на каждом уровне для каждой позиции мы считали количество минимумов на подотрезке, начинающемся или заканчивающемся в этой позиции, поэтому мы можем завести массив $S[n][\log n]$, где $S[i][j]$ равно как раз паре из минимума и количеству минимумов на подотрезке, начинающемся или заканчивающимся в позиции $i$ на $j$-й глубине рекурсии.

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

Для начала научимся отвечать на запрос количества минимумов на подотрезке с позиции $l$ до позиции $r$ за $O(\log n)$. Посмотрим на середину массива (по которой мы делили на первом уровне рекурсии). Если она между $l$ и $r$, то мы знаем количество минимумов на подотрезке от $l$ до середины ($S[l][0]$) и количество минимумов на подотрезке от середины до $r$ ($S[r][0]$). Таким образом можно взять количество минимумов на всём отрезке. Если же середина лежит не между $l$ и $r$, то весь подотрезок с $l$ по $r$ лежит либо в первой, либо во второй половине массива. Тогда мы можем повторить те же рассуждения уже для половины массива, т.е. посмотреть на середину массива, проверить, лежит ли середина этой половины между $l$ и $r$, если да, то взять ответ на основе $S[l][1]$ и $S[r][1]$, а если нет, то рекурсивно запустится уже для четверти нашего массива и так далее.

Описанный выше способ ответа на запрос очень напоминает дерево отрезков, и ничем не лучше его по асимптотике. Попробуем его ускорить. По сути, нам надо найти такое $k$, что если разделить массив на подотрезки длиной $2^k$, то $l$ и $r$ лежат в одном подотрезке, а если разделить массив на подотрезки длиной $2^{k + 1}$, то $l$ и $r$ лежат в разных подотрезках. Заметим, что если мы посмотрим на позиции начал подотрезков

Допишу потом.