Друзья, практический вопрос надо счиать скользящую медиану в последовательности по заданному

окну (длины N)
тупой вариант - взять значения в окне, отсортировать, взять элемент посередине

можно как-то ускорить? например взять какую-то структуру (какую?), чтобы добавить и удалять из нее элемент, сохраняя отсортированность, можно было за log(N)
и можно было получить этот самый средний элемент

Прошитое дерево

ссылку?

две разделённые хипы размером в половину окна?

Как это будет работать?

если все элементы первой хипы <= всех элементов второй, то в корне лежит медиана

Просто сет размером с окно?

Это "классика", нет? https://ru.wikipedia.org/wiki/Алгоритм_выбора

Нет, quick select это O(w), получится O(n*w). Традиционный способ — балансировать два мультисета, или два хипа (нестандартных, с быстрой заменой). tc = O(n log w), sc = O(w)

Нужны хешмапы видимо, чтобы находить элемент внутри хипа

На литкоде есть. https://leetcode.com/problems/sliding-window-median/

это прекрасно

И собственно там можно посмотреть разные решения. Целевая сложность - O(nlogk) время, O(k) - память, если не считать память на ответ.

а зачем два, еще раз?

Два ~одинакового размера, в одном все значения меньше второго.

Вопрос в чем проблема сделать один

При чём тут конкретно quickselect? ;) Я имел в виду, что сама проблема (и её вариации) "классическая" (и алгоритмы давно известны), и дал ссылку на её название. Даже в английской версии той же статьи есть: "For a collection of data values undergoing dynamic insertions and deletions, the order statistic tree augments a self-balancing binary search tree structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the k-th element in the current set to all be performed in O(log n) time per operation.[2] Going beyond the comparison model of computation, faster times per operation are possible for values that are small integers, on which binary arithmetic operations are allowed.[32] It is not possible for a streaming algorithm with memory sublinear in both n and k to solve selection queries exactly for dynamic data..."

Один раз посчитать медиану окна, а дальше просто пересчитывать под изменения ? Окна ведь перекрывающиеся ? Если так, то после одной сортировки в N каждая следующая будет зависеть от дельты окна. Вопрос структуры имеет смысл только, если вы это делаете постоянно или если размер окна очень велик. Если же это так, то есть алгоритм быстрой медианы за линейку https://habr.com/ru/articles/346930/