SRM 310 DIV 2 1000

Я так понял тебе нужно искать на каждом отрезке 1..k, 2..k+1, 3..k+2 => средний элемент или медиану (если отсортировать отрезок и взять в нём элемент стоящий по середине, то это и будет медианой).
Если это так, то можно написать такое решение:
Сожмём числа если они большие (и того получим числа от 1..n), теперь создадим как ты и сказал дерево Фенвика(или сумматор по другому), занесём первые k-1 элементов в сумматор,то есть на их позиции по прибавляем +1 (если одинаковые элементы имеются то на них будет стоять больше 1). Теперь что,начинаем бежать с i = с k .. n элемент, добавляем на позицию i - го числа в сумматоре(дерево Фенвика) +1,теперь что все наши числа в отрезке длиной k в сумматоре,начнём перебирать дихотомией какой элемент будет ответом на данном отрезке,и смотрим если сумма от 1..Middle(текущая позиция дихотомии) >= k / 2, то меняем правый край дихотомии,иначе левый.
И того Middle и будет нашим ответом,так как сумма до него равна k/2. И следовательно в данном отрезке он будет медианой.

Memory: O(N)
Time: O(N*log(N)*log(N)).

Зачем себе голову забивать,пиши дихотомия+сумматор самое распространённое.