Алгоритмы поиска медианы на подотрезках [Игнатий Колесниченко 10.10.2019]

На докладе рассказывается про задачу построения структуры данных для эффективного поиска медианы на подотрезках заданного массива. Задача имеет простое решение в модели сравнений за O(n log k + k log n), где n - это размер массива, а k – количество запросов на поиск медианы. В указанном решении применяются стандартные техники, и кажется удивительным, что оно появилось только в статье 2009 года. Также я расскажу про результаты в данной задаче для RAM-модели, где комбинацией несложных идей и эффективных структуры данных авторы статьи научились строить компактную структуру данных, которая умеет отвечать на запрос поиска медианы на подотрезке за время O(log n / log log n). Доклад основывается на статье: * Towards Optimal Range Medians, G. Brodal, B. Gfeller, A. Jørgensen1, and P. Sanders.