Merge sort tree
Задача
Дан массив $a_0,\ \ldots,\ a_{n-1}$. Требуется ответить на $q$ запросов:
- $?\ l,\ r,\ x$ — количество элементов на $a_l,\ \ldots,\ a_r$, меньших $x$.
Решение
Если подотрезок массива отсортирован, то мы умеем отвечать на такой запрос за $O(\log n)$ с помощью бинпоиска. Построим дерево отрезков на нашем массиве, а в каждой вершине будем хранить отсортированную версию соответствующего подотрезка массива. Тогда ответ на запрос работает за $O(\log^2 n)$ — мы делаем обычный get-запрос в дереве отрезков, отличающийся лишь получением ответа на подотрезке, потому что там мы будем делть бинпоиск.
Построение
Для того, чтобы быстро построить merge sort tree, воспользуемся идеей merge sort'а (собственно, отсюда и название). Для каждой вершины будем хранить копию ее подотрезка (о затратах на память поговорим позже). Если вершина отвечает за отрезок длины 1, то ее массив уже отсортирован. А если у сыновей вершиины отсортированы массивы, то мы их можем просто слить за линейное время.
Время работы и используемая память
Каждый элемент массива будет храниться в $O(\log n)$ массивах — на пути от листа до корня, поэтому наша структура будет занимать $O(n \log n)$ памяти. Построение работает за $O(n \log n)$ (см. [Сортировка слиянием#Асимптотика]), а ответ на запрос за $O(\log^2 n)$.
Тут скоро появится реализация.
Версия данной задачи с запросами изменения потребует более тяжелых структур.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s