Диапазон Минимальный / Максимальный Запрос

Question

У меня есть координаты (x, y), скажем, у меня есть 10 000 точек.теперь, когда в качестве тестового запроса указывается новая точка (p, q).Я должен проверять каждую точку в координатных точках. Если x координата текстового запроса, который является PY, из онлайн-поиска, я узнал, что структура данных минимального / максимального диапазона Rmq может помочь мне, но я не уверен, как это сделать ..Может ли кто-нибудь помочь мне, как я могу сделать это .. любые ссылки или помощь в коде в C ++ будут очень полезны. спасибо

Answer 1

Если ваша цель - проверить, существует ли точка в наборе данных, есть ряд действительно полезных структур данных, которые вы можете использовать для хранения данных, каждая из которых поддерживает очень эффективный поиск.

Для начала, если вам нужно только знать, существует ли точка, вы всегда можете сохранить все точки в стандартной хеш-таблице или сбалансированном бинарном дереве поиска. Это даст время поиска O (1) или O (log n) соответственно. Кроме того, эти структуры, как правило, доступны в большинстве языков программирования.

Если, с другой стороны, вы планируете выполнять более сложные операции с данными, такие как поиск k точек в наборе данных, ближайших к некоторой контрольной точке, или попытка найти все точки в некоторой ограничивающей области Возможно, вы захотите использовать kd-tree или quadtree . Эти варианты в стандартном бинарном поиске предлагают быстрый поиск (O (log n) время). Kd-дерево также поддерживает очень быстрый k-ближайший сосед поиск и поиск внутри ограничивающих томов. Более того, kd-дерево на удивление легко реализовать, если у вас есть опыт реализации стандартного бинарного дерева поиска.

Надеюсь, это поможет!