Тема: Быстрый поиск среднего элемента.
Люди!
Подскажите, как можно решить следующую проблему:
Дана последовательность целых чисел.
Поступаю запросы на нахождения среднего элемента а отрезке [l; r].
Средним элементом в последовательности 0..n - 1 называют такой элемент, который имеет позицию (n - 1) / 2 в данной упорядоченной последовательности.
Как можно быстро находить такие элементы?
Заранее спасибо!