Сведение задачи RMQ к задаче LCA
Постановка задачи RMQ
Дан массив . Поступают запросы вида , на каждый запрос требуется найти минимум в массиве , начиная с позиции и заканчивая позицией .
Алгоритм
Декартово дерево (англ. сartesian tree) на массиве — это бинарное дерево, рекурсивно определенное следующим образом:
- Корнем дерева является минимальное значение в массиве , скажем . Если минимальных значений несколько, можно взять любое.
- Левым поддеревом является декартово дерево на массиве .
- Правым поддеревом является декартово дерево на массиве .
Построим декартово дерево на массиве . Тогда = .
Доказательство
Мы знаем что:
- Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок или меньше их самих.
- ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив и находится между и . То есть является
Построение дерева за линейное время
Пусть дан массив . Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение , начнем обход из вершины к корню, пока не найдем вершину , для которой . Тогда правого сына назначим левым сыном , а — правым сыном . Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более раз и итоговая асимптотика алгоритма .
Сложность
Выше описан алгоритм построения дерева за . Препроцессинг для — и ответ на запрос . В итоге получили {построение , запрос }.
