Недавно столкнулся с задачей, частью которой был доступ к медиане за О(logN) максимум, при этом элементы добавляются/удаляются по-одному и медиана нам нужна будет только тогда когда кол-во элементов в нашем списке равно какому-то М. Мне когда-то говорили что это можно делать при помощи нескольких деревьев Фенвика, но хотелось бы узнать какой-то более оптимальный способ. Я пробовал это делать при помощи сета с итератором на середину, но по-ходу я понял что этот итератор я не умею двигать.

UPD. хотелось бы также узнать можно ли решать более обобщенные задачи, например узнать медиану на отрезке от L до R.