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

• Задача "Рейч медиан к" названа так из-за сложности и ассоциаций с другими задачами.  

• В докладе был заявлен простой комбинаторный алгоритм, но он оказался сложным для понимания.  

• Егор предложил простое решение, которое оказалось эффективным.  

• Задача заключается в нахождении медианы на отрезке чисел.  

• Задача была придумана автором для домашнего задания.  

• Медиана на отрезке определяется как элемент, который делит отрезок пополам.  

• Задача кажется сложной, но на самом деле она проста.  

• Автор считает, что задача может быть решена на олимпиадах.  

• Решение основано на двух статьях 2009-2011 годов.  

• Задача включает две части: эффективное представление массива и быстрое выполнение запросов.  

• Обозначение: k - количество запросов.  

• Массив делится на две равные части: элементы меньше медианы и элементы больше медианы.  

• Элементы переносятся в соответствующие подмассивы, сохраняя порядок.  

• Запрос на медиану на отрезке переформулируется в аналогичный запрос для подмассивов.  

• Медиана находится в подмассиве, где больше половины элементов.  

• Рекурсивная функция ищет не только медиану, но и порядковую статистику.  

• Структура данных напоминает двоичное дерево.  

• Алгоритм был предложен в 2009 году, но идея была известна ранее.  

• Массив делится на две части, затем процесс повторяется.  

• Запрос путешествует по массиву, переходя между частями.  

• Оценка времени построения и ответа на запрос.  

• Построение структуры данных занимает линейное время.  

• Количество слоев логарифмическое.  

• Внизу отсортированный массив из единичных элементов.  

• Хранение элементов и индексов в явном виде.  

• Бинарный поиск для нахождения индекса элемента.  

• Время работы логарифм плюс логарифм пополам плюс логарифм на четыре.  

• Использование указателей для быстрого перехода.  

• Сохранение индексов элементов в массиве.  

• Время работы логарифм времени.  

• Применение структуры данных к заранее известным запросам.  

• Время работы логарифм плюс кф дво.  

• Ленивое разбиение массива для каждого запроса.  

• Подсчет действий на каждом уровне дерева.  

• Определение количества разбиений на каждом уровне.  

• Суммирование времени, затраченного на разбиения.  

• Суммирование времени по уровням дерева.  

• Подсчет количества кусков на каждом уровне.  

• Умножение стоимости разбиения на количество кусков.  

• Экономия времени на нижних уровнях дерева.  

• Минимум между количеством запросов и количеством разбиений.  

• Разбиение суммы на две части: первая сумма и хвост.  

• Оценка снизу для модели сравнения.  

• Экономия памяти в модели экономики.  

• Применение битовых масок для экономии памяти.  

• Динамические случаи и их обработка.  

• Использование связанного списка для хранения элементов.  

• Запросы на медиану и порядковые статистики.  

• Запросы на вставку и удаление элементов.  

• Использование бинарного дерева для обработки запросов.  

• Разделение списка на две части по медиане.  

• Обсуждение поиска медианы в потер модели.  

• Сомнения в линейности алгоритма.  

• Проблемы с балансировкой и перекос структуры.  

• Трудности с обновлением медианы.  

• Возможность использования другого элемента для деления.  

• Частичная сбалансированность дерева.  

• Проблема с запросом на расстояние между элементами.  

• Использование дерева для подсчета элементов.  

• Сложность и поддержка сбалансированного дерева.  

• Идея списка с порядковым номером.  

• Проблемы с сохранением структуры дерева.  

• Необходимость поддержки пойнтов и номеров уровней.  

• Введение альфа-баланса.  

• Цель: минимизировать разницу между размерами левого и правого поддеревьев.  

• Амортизированная оценка на вставку и удаление.  

• Перестройка дерева при нарушении баланса.  

• Линейное время на перестройку.  

• Возможность перестройки структуры вместе с деревом.  

• RAM позволяет делать сложные операции с учетом комментариев и полнотой статей.  

• Объяснение работы RAM требует много времени и усилий для полного понимания.  

• RAM использует битовые трюки для быстрого спуска по дереву.  

• RAM позволяет быстро спускаться по дереву, но требует больше памяти.  

• Вставка и удаление элементов в RAM усложняют процесс.  

• RAM не строит деревья, а использует массивы для хранения данных.  

• Рассматривается задача нахождения медианы в массиве.  

• Размер массива и время выполнения запросов зависят от случайной перестановки элементов.  

• Важно учитывать вероятность успешного выполнения запросов.  

• Рассматривается подзадача с массивом и случайной перестановкой элементов.  

• Строится структура данных для ответа на запросы медианы.  

• Медиана всегда лежит в определенном подмассиве.  

• Массив разбивается на три части, и медиана находится в центре.  

• Медиана не сильно меняется при перемещении границ массива.  

• Медиана всегда лежит в подмассиве, который можно вычислить за O log n времени.  

• Рассматривается множество элементов, которые не попадают в ответ.  

• Ожидание таких элементов равно O log n.  

• Это позволяет упростить структуру данных и улучшить производительность.  

• Рассматривается вероятность попадания элементов в определенный диапазон.  

• Вводятся иксы, которые могут вмешиваться в процесс.  

• Обсуждается, как обрабатывать элементы с иксами, учитывая их влияние.  

• Иксы считаются константой, что упрощает задачу.  

• Рассматривается возможность решения задачи с учетом икс-элементов.  

• Обсуждается, как учитывать икс-элементы при расчете ответа.  

• Фиксируются иксы и их влияние на ответ.  

• Строится таблица размеров для каждого икс-элемента.  

• Обсуждается необходимость умножения икс-элементов для получения ответа.  

• Рассматривается выбор отрезка для ответа, учитывая влияние икс-элементов.  

• Обсуждается, что икс-элементы не могут сильно сдвинуть ответ.  

• Выбирается отрезок нужного размера для точного ответа.  

• Икс-элементы сравниваются с выбранным отрезком.  

• Обсуждается, как учитывать икс-элементы при расчете ответа.  

• Рассматривается, как дополнительные временные расходы влияют на процесс.  

• Научились отвечать на запросы для любых икс-элементов.  

• Необходимо построить набор подотрезков для покрытия всех запросов.  

• Обсуждается, как разбить отрезок на куски для точного ответа.  

• Отрезок разбивается на куски с шагом.  

• Рассматривается, как выбрать отрезок для ответа.  

• Обсуждается, как сохранить соотношения между отрезками.  

• Строится массив для фиксированных расстояний.  

• Рассматриваются структуры данных для различных расстояний.  

• Обсуждается, сколько структур данных понадобится для покрытия всех запросов.  

• Обсуждение построения структуры данных для фиксированного значения m.  

• Каждая структура занимает порядка m^2 памяти.  

• Построение структуры данных для каждого значения m.  

• Оценка размера одного семейства структур данных.  

• Суммарный размер структуры данных зависит от m.  

• Основное время тратится на сортировку центральной части.  

• Обсуждение проблемы нахождения медианы в скользящем окне.  

• Необходимость построения медианы для каждого значения m.  

• Оценка времени и памяти для различных структур данных.  

• Рассмотрение использования деревьев для решения задачи.  

• Обсуждение фиксированных и скользящих окон.  

• Оценка статических и динамических структур данных.  

• Подведение итогов обсуждения.  

• Упоминание известных авторов и статей.  

• Благодарность за участие.