Недавно столкнулся с задачей, частью которой был доступ к медиане за О(logN) максимум, при этом элементы добавляются/удаляются по-одному и медиана нам нужна будет только тогда когда кол-во элементов в нашем списке равно какому-то М. Мне когда-то говорили что это можно делать при помощи нескольких деревьев Фенвика, но хотелось бы узнать какой-то более оптимальный способ. Я пробовал это делать при помощи сета с итератором на середину, но по-ходу я понял что этот итератор я не умею двигать.
UPD. хотелось бы также узнать можно ли решать более обобщенные задачи, например узнать медиану на отрезке от L до R.
Можно хранить маленькие элементы в одном сете, а большие во втором. При добавлении/удалении поддерживать разницу размеров сетов не более 1. Медиана — последний элемент первого сета или первый второго.
Можно хранить все в одном сете, и поддерживать значение медианы. Когда нужно, заменять его на следующее или предыдущее в сете. При этом не хранить итератор на это значение, а просто каждый раз находить заново.
L и R — это что? Значения элементов? Или какие-то индексы?
Имелось в виду элементы с индексами от L до R.
На отрезке — в оффлайне есть стандартное решение за N*sqrt(N)*log(N), как и во всех задачах такого типа — с корневой и +- переходами.
Разбиваем запросы на группы по левому краю (в первой те, у которых левый край <=sqrt, во второй — те, у которых <=2*sqrt, и так далее), в каждой группе делаем сортировку по правому краю — и далее решаем нашу начальную задачу для всех отрезков по очереди — один переход мы умеем делать за логарифм, а переходов в общей сложности получится не более N*sqrtN для левых концов и еще N*sqrtN для правых. Для правых оценка получается такой, потому что в каждом блоке, благодаря сортировке, переходы правых концов будут только вправо, следовательно — их будет не более N суммарно для блока. Для левых — потому что мы соответствующим образом разбили запросы на блоки, и левый конец в пределах блока "танцует" на отрезке длиной sqrt.
Можно за O(log(n)):
http://codeforces.net/blog/entry/2954#comment-59840
Обычную медиану можно и вовсе на одном сете находить.
Нужно лишь хранить итератор, указывающий собственно на медиану, и при каждом добавлении/удалении элемента при необходимости сдвигать этот итератор на один элемент влево или вправо.
Извиняюсь, не заметил, что выше точно такое уже написали =(