У меня есть набор S элементов типа T. Существует частичный порядок <= на элементах типа T. Известно, что все элементы в S не упорядочены. Затем мне нужен способ выполнить следующий запрос: имея элемент e типа T, найти e' в S такое, что e <= e'.
Существует ли структура данных, которая позволяет эффективно выполнять такие запросы (без линейного сканирования S)?
Важное примечание: T представляет собой полную решетку.
Вы можете предварительно обработать список и найти подмножество элементов, у которых нет других элементов, превышающих эти числа (предположим, что вы представили все числа в виде дага, вы должны найти все элементы, у которых нет родителей). Когда у вас есть это подмножество, все, что вам нужно сделать, это линейное сканирование этого подмножества. Я не думаю, что вы можете сделать лучше, чем это.
Кроме того, вы также можете отсортировать это подмножество по количеству элементов, каждый из которых в подмножестве больше (в порядке убывания). И сканируйте элементы по порядку.
