Проектирование структуры данных, которая работает за O (logn) времени

Question

Я проверяю этот класс алгоритмов для работы и пытаюсь решить некоторые практические задачи, приведенные в классе.Эта проблема поставила меня в тупик, и я просто не могу обернуться вокруг нее.Ни одно из моих решений не вышло за время.Может ли кто-нибудь помочь мне с этой проблемой ??

Вопрос: Предположим, что нам дана последовательность из n значений x1, x2, ..., xn в произвольном порядке и мы хотим быстро ответить на повторяющиеся запросы вида: для произвольной пары i и j с 1 ≤ i

Answer 1

Для ввода a1, a2, a3, ... an создайте узел, который содержит минимум (a1, .., ak) и минимум (ak + 1, .., an), где k = n /2.

Рекурсивно построить остальную часть дерева.

Теперь, если вы хотите найти минимум между ai и aj:

1. Определите наименьшего общего предкаиз я, j.Пусть это будет k
2. Начните с i и продолжайте двигаться, пока не нажмете k.На каждой итерации проверяют, был ли дочерний узел левым.Если да, то сравните min правого поддерева и обновите текущий min соответствующим образом.
3. Аналогично, для j проверьте, является ли он правым узлом ....
4. В узле k сравните значения, возвращаемые каждымподдерево и возврат мин.

Answer 2

Люди обдумывают это.Предположим, что вы начинаете со списка:

47, 13, 55, 29, 56, 9, 17, 48, 69, 15

Составьте следующий список списков:

47, 13, 55, 29, 56, 9, 17, 48, 69, 15
13,     29,     9,     17,     15
13,             9,             15
9,                             15
9

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

Answer 3

Попытка объяснить предлагаемую структуру данных:

Для каждой пары чисел вычислите и сохраните значение меньшего.Для каждых четырех последовательных чисел рассчитайте и сохраните значение наименьшего из четырех.Это делается быстро, выбирая меньшее из двух парных значений.Для каждых восьми последовательных чисел рассчитайте и сохраните значение наименьшего из восьми.И так далее.

Допустим, мы хотим наименьшее значение от x19 до x65.

Мы рассмотрим следующие сохраненные значения: Наименьшее из x32 до x63Наименьшее из х24 до х31.Наименьшее из х20 до х23.x19.Наименьшее из x64 до x65.

Затем мы выбираем самый маленький из них.

Answer 4

Вопрос задавался ранее несколько иным способом: Какую структуру данных, использующую O (n) хранилище с O (log n) временем запроса, я должен использовать для Range Minimum Queries?

Тем не менее, чтобы быстро ответить, проблема, с которой вы сталкиваетесь, хорошо изучена - Минимальный диапазон запросов. Дерево сегментов - это структура данных, которая может решить проблему с O (N) пространством и O (logN) требованиями к времени. Вы можете увидеть более подробную информацию в здесь , где есть объяснение структуры и сложности.

Answer 5

Я думаю, что решающим шагом является то, что вам нужно будет отсортировать данные заранее. Затем вы можете хранить данные в массиве / списке. Затем вы можете выполнить быстрый двоичный поиск в O (logn), выбрав первое значение, которое удовлетворяет условию (я предполагаю, что вы имели в виду между xi и xj, а не x1 и xj).

edit: если подумать, то, чтобы значение удовлетворяло условию, может быть не таким тривиальным, как я думал