Изменения

Для нахождения минимального элемента на отрезке можно использовать [[Дерево отрезков. Построение|дерево отрезков]]. Длина массива глубин будет равна <tex>(2n - 1),</tex> , т.е. дерево отрезков будет построено можно построить за <tex>O(n).</tex> Таким образом, препроцессинг работает за <tex>O(n).</tex> Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. <tex>O(\log n).</tex>