Запросы по массиву

Question

Вам предоставляется массив из N натуральных чисел, A1, A2, ..., An. Вы должны ответить на Q-запросы. Каждый запрос состоит из двух целых чисел L и K. Для каждого запроса я должен указать элемент Kth, который больше или равен L в массиве, когда все такие элементы перечислены в соответствии с возрастающим порядком их индексов.

Пример A = 22,44,12,16,14,88,25,49

Запрос 1: L = 3 К = 4 Поскольку все элементы больше 3. Таким образом, мы перечислить весь массив т.е. 22,44,12,16,14,88,25,49. 4-й элемент среди этих элементов составляет 16

Запрос 2: L = 19 K = 5 Элементы, включенные в список 22,44,88,25,49. Пятый элемент среди них 49.

Что я сделал: для каждой итерации запроса по всему массиву и проверить элемент, который является k-ю больше или равна L. Сложность: O (Q * N)

Что мне нужно: сложность O (Q * logN).

Ограничения: 1 < = Q < = 10^5 1 < = N < = 10^5 1 < = Ai < = 10^5

Answer 1

Один из возможных способов решения этой задачи является использование неизменяемыми двоичное (RB) дерево.

Сначала вам нужно отсортировать массив в порядке возрастания, сохраняя исходные индексы элементов рядом с элементами.

Перемещение массива в обратном порядке (по убыванию), добавление элементов один за другим до неизменяемый бинарное дерево. Ключ в дереве: оригинальный индекс элемента. Дерево является неизменным, поэтому, добавляя элемент, я имею в виду создание нового дерева с добавленным элементом. Сохраните дерево, созданное на каждом шаге рядом с соответствующим элементом (элемент, который был добавлен последним в дерево).

Имея эти деревья, построенные для каждого элемента, вы можете выполнять свои запросы в O (log N) времени.

Запрос: Во-первых, выполнить бинарный поиск для L в отсортированном массиве (O (N журнал)) для элемента, который больше, чем L. Вы найдете элемент и соответствующее дерево индексов элементов, которые больше L. В этом дереве вы можете найти K -й самый большой индекс в O (log N) времени.

Весь алгоритм будет принимать время O (N log N + Q log N). Я не верю, что можно сделать лучше (поскольку сортировка исходного массива кажется неизбежной).

---

Ключом этого подхода является использование неизменяемого двоичного дерева. Эта структура разделяет свойства изменяемого двоичного дерева, такие как вставка и поиск в O (log N), оставаясь неизменной. Когда вы добавляете элемент в такое дерево, предыдущая версия дерева сохраняется, воссоздаются только узлы, которые отличаются от предыдущей «версии» дерева. Обычно это O (log N) узлы. Таким образом, для создания N деревьев из элементов вашего массива потребуется время O (N log N) и O (N log N).

Вы можете использовать immutable RB tree implementation in Scala в качестве ссылки.