Изменения

Для нахождения минимального элемента на отрезке можно использовать [[Дерево отрезков. ПостроениеАлгоритм Фарака-Колтона и Бендера|дерево отрезковалгоритм Фарака-Колтона и Бендера]]. Длина массива глубин будет равна для <tex>(2n - 1)\pm 1RMQ</tex>, т. ек. соседние элементы в списке глубин отличаются не более чем на единицу. дерево отрезков можно построить за Длина списка глубин составляет <tex>O(n2n - 1).</tex> Таким , таким образом, препроцессинг работает за <tex>O(n).</tex> . Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т. е. {{---}} <tex>O(\log n1).</tex>.