Минимальный уровень Kth в диапазоне

Ответ 1

Вот решение O(polylog n) для каждого запроса, которое фактически не принимает константу k, поэтому k может варьироваться между запросами. Основная идея состоит в том, чтобы использовать дерево сегментов, где каждый node представляет интервал индексов массива и содержит мультимножество (сбалансированное двоичное дерево поиска) значений в представленном сегменте массива. Операция обновления довольно проста:

• Поднимите дерево сегментов из листа (обновляемый индекс массива). Вы столкнетесь со всеми узлами, которые представляют интервал индексов массива, который содержит обновленный индекс. На каждом node удалите старое значение из мультимножества и вставьте новое значение в мультимножество. Сложность: O(log^2 n)
• Обновите массив.

Мы заметили, что каждый элемент массива будет находиться в O(log n) мультимножествах, поэтому общее использование пространства O(n log n). С линейным объединением мультимножеств мы можем также построить начальное дерево сегментов в O(n log n) (там O(n) работа за уровень).

Как насчет запросов? Нам задан диапазон [i, j] и ранг k, и мы хотим найти k-й наименьший элемент в a[i..j]. Как мы это делаем?

• Найдите непересекающийся охват диапазона запросов с использованием стандартной процедуры запроса дерева сегментов. Мы получаем O(log n) непересекающиеся узлы, объединение мультимножеств которых является точно мультимножеством значений в диапазоне запросов. Назовем эти мультимножества s_1, ..., s_m (с m <= ceil(log_2 n)). Поиск s_i занимает время O(log n).
• Сделайте запрос select(k) в объединении s_1, ..., s_m. См. Ниже.

Итак, как работает алгоритм выбора? Для этого есть один очень простой алгоритм.

У нас есть s_1, ..., s_n и k, и мы хотим найти наименьший x в a, так что s_1.rank(x) + ... + s_m.rank(x) >= k - 1, где rank возвращает количество элементов, меньших, чем x, в соответствующем BBST (это можно реализовать в O(log n), если мы сохраним размеры поддерева). Позвольте просто использовать двоичный поиск, чтобы найти x! Мы проходим через BBST корня, делаем пару ранговых запросов и проверяем, больше ли их сумма или равна k. Это предикат монотонности в x, поэтому работает бинарный поиск. Тогда ответом является минимум преемников x в любом из s_i.

Сложность: O(n log n) предварительная обработка и O(log^3 n) для каждого запроса.

Таким образом, мы получаем время выполнения O(n log n + q log^3 n) для q запросов. Я уверен, что мы сможем получить его до O(q log^2 n) с помощью более гибкого алгоритма выбора.

ОБНОВЛЕНИЕ: Если мы ищем автономный алгоритм, который может обрабатывать все запросы одновременно, мы можем получить O((n + q) * log n * log (q + n)), используя следующий алгоритм:

• Предварительно обработать все запросы, создать набор всех значений, которые когда-либо происходили в массиве. Их число будет не более q + n.
• Создайте дерево сегментов, но на этот раз не на массиве, а на множестве возможных значений.
• Каждый node в дереве сегментов представляет собой интервал значений и поддерживает набор позиций, в которых происходят эти значения.
• Чтобы ответить на запрос, начните с корня дерева сегментов. Проверьте, сколько позиций в левом дочернем элементе корня находится в интервале запросов (мы можем сделать это, выполнив два поиска в BBST позиций). Пусть это число m. Если k <= m, запишите в левый ребенок. В противном случае recurse в правый ребенок, с k уменьшенным на m.
• Для обновлений удалите позицию из узлов O(log (q + n)), которые покрывают старое значение и вставляют его в узлы, которые покрывают новое значение.

Преимущество этого подхода заключается в том, что нам не нужны размеры поддерева, поэтому мы можем реализовать это с большинством стандартных реализаций библиотек сбалансированных двоичных деревьев поиска (например, set<int> в С++).

Мы можем превратить это в онлайн-алгоритм, изменив дерево сегментов для взвешенного по весу дерева, такого как дерево BB [α]., Он имеет логарифмические операции, такие как другие сбалансированные двоичные деревья поиска, но позволяет нам восстанавливать все поддеревье с нуля, когда он становится несбалансированным, заряжая стоимость восстановления для операций, которые должны были вызвать дисбаланс.

Ответ 2

Если это проблема программирования, вы можете уйти со следующим алгоритмом O (n log (n) + q n ^ 0.5 log (n) ^ 1.5). Он настроен на то, чтобы хорошо использовать С++ STL и имеет гораздо лучшую константу big-O, чем ответ Niklas (предыдущий?), Учитывая гораздо меньшее пространство и косвенность.

Разделите массив на k кусков длины n/k. Скопируйте каждый фрагмент в соответствующие местоположения второго массива и отсортируйте его. Чтобы обновить: скопируйте фрагмент, который был изменен во второй массив, и отсортируйте его снова (время O ((n/k) log (n/k)). Чтобы запросить: скопировать в массив царапин не более 2 (n/k - 1) элементы, принадлежащие фрагменту, частично перекрывающие интервал запроса. Сортируйте их. Используйте один из ответов на этот вопрос, чтобы выбрать элемент запрашиваемого ранга из объединение отсортированного массива нуля и полностью перекрывающихся кусков во времени O (k log (n/k) ^ 2). Оптимальная установка k в теории - это (n/log (n)) ^ 0,5. log (n) ^ 0,5, используя сложный алгоритм Фредериксона и Джонсона.

Ответ 3

выполните модификацию сортировки ведра: создайте ведро, которое содержит числа в нужном вам диапазоне, а затем отсортируйте это ведро и найдите k-й минимум.

Ответ 4

Черт, это решение не может обновить элемент, но, по крайней мере, находит k-й элемент, здесь вы получите некоторые идеи, чтобы вы могли подумать о каком-то решении, которое обеспечивает обновление. Попробуйте B-деревья на основе указателей.

Это O (n log n) и O (q log ^ 2 n). Позже я объяснил это с помощью O (log n) для каждого запроса.

Итак, вам нужно сделать следующее:

1) Создайте "сегментное дерево" по заданному массиву.

2) Для каждого node вместо хранения одного номера вы сохраните целый массив. Размер этого массива должен быть равен числу его детей. Этот массив (как вы уже догадались) должен содержать значения нижних узлов (дочерние элементы или числа из этого сегмента), но отсортирован.

3) Чтобы создать такой массив, вы объедините два массива из двух своих сыновей из дерева сегментов. Но не только это, для каждого элемента из массива, который вы только что создали (путем слияния), вам нужно запомнить позицию номера перед его вставкой в ​​объединенный массив (в основном, массив, из которого он приходит, и положение в нем), И указатель на первый следующий элемент, который не вставлен из того же массива.

4) С помощью этой структуры вы можете проверить, сколько номеров там меньше заданного значения x, в каком-либо сегменте S. Вы находите (с бинарным поиском) первое число в массиве корня node, которое >= х. И затем, используя указатели, которые вы сделали, вы можете найти результаты для одного и того же вопроса для двух дочерних массивов (массивы узлов, которые являются дочерними для предыдущего node) в O (1). Вы прекращаете работать с этим нисходящим для каждого node, который представляет сегмент, который является целым либо внутри, либо вне данного сегмента S. Сложность времени - это O (log n): O (log n), чтобы найти первый элемент, который является >= x и O (log n) для всех отрезков разбиения S.

5) Сделайте бинарный поиск по решению.

Это было решение с O (log ^ 2 n) на запрос. Но вы можете уменьшить до O (log n):

1) Прежде чем делать все, что я написал выше, вам нужно преобразовать проблему. Вам нужно отсортировать все номера и запомнить позиции для каждого в исходном массиве. Теперь эти позиции представляют собой массив, над которым вы работаете. Вызовите этот массив P.

Если границы сегмента запроса - a и b. Вам нужно найти k-й элемент в P, который находится между a и b по значению (не по индексу). И этот элемент представляет индекс вашего результата в исходном массиве.

2) Чтобы найти этот k-ый элемент, вы бы сделали некоторый тип обратного слежения со сложностью O (log n). Вы будете запрашивать количество элементов между индексом 0 и (некоторым другим индексом), которые находятся между значениями a и b.

3) Предположим, что вы знаете ответ на такой вопрос для некоторого отрезка (0, h). Получайте ответы на одни и те же вопросы для всех сегментов в дереве, начинающихся с h, начиная с самого большого. Продолжайте получать ответы до тех пор, пока текущий ответ (из сегмента (0, h)) плюс ответ, который вы получили последним, больше, чем k. Затем обновите h. Продолжайте обновлять h, пока в дереве не будет только одного сегмента, начинающегося с h. Это h является индексом числа, которое вы ищете в проблеме, о которой вы заявили.

Чтобы получить ответ на такой вопрос для некоторого сегмента из дерева, вы будете тратить точно O (1) времени. Поскольку вы уже знаете ответ этого родительского сегмента и используя указатели, которые я объяснил в первом алгоритме, вы можете получить ответ для текущего сегмента в O (1).