Минимум на неизменяемом отрезке



Дан массив из N целых чисел и K запросов, состоящих из двух индексов.
Необходимо для каждого запроса вывести минимальный из элементов, расположенных между индексами в запросе.


 Есть несколько способов решения этой задачи:


    Динамическое программирование O(N2 + K)

    Дерево отрезков O(NlogN + KlogN)

    Sparse Table O(NlogN + K)




18:14
04.08.2009


По всем вопросам обращаться: rumterg@gmail.com