Структура для быстрого поиска "меньшего" массива

[B@R5uk]

Есть набор векторов (массивов) одинаковой длины с неотрицательными целыми числами в качестве элементов. Я их буду записывать в виде столбцов a матрицы, но вообще это просто массивы типа int [] в памяти. И есть другой вектор b, для которого надо найти столбец из набора, который будет поэлементно не превосходить вектор b. Например, в следующей матрице слева от вертикальной черты находятся вектора набора, а справа — вектора, для которых ищется не превосходящий элемент:

$$\begin{array}{cccccccc|ccc} a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&b_1&b_2&b_3&\hline 6&5&2&0&0&0&0&0&9&2&0\\ 0&0&2&6&4&3&0&0&1&3&6\\ 0&2&0&0&0&0&6&3&5&0&5\\ 2&5&0&0&4&0&0&4&1&1&4\\ \end{array}$$

Вектор $b_2$ в качестве не превосходящих имеет вектора $a_3$ и $a_6$, вектор $b_3$ — вектора $a_4$, $a_5$, $a_6$ и $a_8$, а вектор $b_1$ вообще не имеет не превосходящих его векторов. Наивный алгоритм будет перебирать вектора набора один за другим и сравнивать все элементы. Это трудоёмкость линейная по количеству векторов.

Поэтому вопрос: существует ли какая-нибудь структура данных, которая бы обеспечивала проверку того, что набор не содержит не превосходящих элементов за время быстрее, чем линейное от числа элементов? В случае наличия одного или нескольких таких элементов, надо выдать хотя бы один какой-нибудь.

-- 03.02.2026, 16:12 --

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

[mathpath]

Теоретически для d≥2 худший случай требует O(n) проверок, потому что если все вектора несравнимы, то любой запрос должен проверить каждый вектор, чтобы убедиться, что нет доминирующего.

Практически можно значительно ускорить в среднем:
Хранить только минимальные вектора (антицепь).
Индексировать их с помощью range tree или R-дерева.
Использовать предварительную фильтрацию по максимуму координат.
Для маленькой размерности (d≤4) range tree даёт O(log^(⁡d−1))*n на запрос.
Для большой размерности придётся мириться с почти линейным временем или использовать приближённые методы.

[zgemm]

Будет статистически хорошо работать кластеризация, то есть для набора своих первых векторов вы ищите плоскость, которая разбивает этот набор на примерно две равные области, но так, чтобы эти области были максимально удалены друг от друга. И далее с каждой такой областью - рекуррентно далее. Всегда надо помнить как плоскость для разбивки, так и направление, вдоль которого все разбито и ширину кластера. Суммарно там вспомогательных чисел примерно в 2 раза больше, чем исходных. Вы прыгаете по кластерам, проверяете попало или нет, если нет, то кластер надо отбросить, если да, прыгать в него дальше. Понятно, что алгоритм не дает в общем случае логарифмическую сходимость, но статистически - очень даже дает. Я им регулярно пользуюсь, чтобы искать ближайшего соседа, обычно при более-менее статистически равномерном распределении от 100 векторов уже такой кластерный алгоритм становится быстрее.

[B@R5uk]

mathpath, zgemm, спасибо за отклик.

zgemm, я так понимаю, ваш подход работает, когда набор векторов более-менее фиксирован? Или же есть метод эффективно обновлять кластеризацию в случае постоянного их обновления (удаления-добавления)?

mathpath, особое спасибо за термины (антицепь и другие). Не совсем понятно, как дерево диапазонов (range tree) можно прикрутить к этой задаче. Оно же специально заточено под построение полного списка элементов, попадающих в указанный диапазон. Я так же из быстрого знакомства не понял, как оно работает в многомерном случае. Подскажите, пожалуйста, какую-нибудь литературу доходчивую почитать по этому поводу?

[mathpath]

B@R5uk в сообщении #1718917 писал(а):

mathpath, особое спасибо за термины (антицепь и другие). Не совсем понятно, как дерево диапазонов (range tree) можно прикрутить к этой задаче. Оно же специально заточено под построение полного списка элементов, попадающих в указанный диапазон. Я так же из быстрого знакомства не понял, как оно работает в многомерном случае. Подскажите, пожалуйста, какую-нибудь литературу доходчивую почитать по этому поводу?

Есть набор точек на плоскости с координатами (x, y).
Ваша задача — найти все точки, у которых x находится в интервале [x1, x2], а y — в интервале [y1, y2].
Главная идея: Свести многомерную задачу к последовательности одномерных.
Первый уровень (по x): Сначала мы быстро находим все точки, которые подходят по координате x.
Второй уровень (по y): Внутри каждого кандидата из первого шага мы быстро проверяем, подходит ли он по координате y.

Конструктивно это реализуется следующим образом:
Основное дерево (по x):
Мы строим сбалансированное двоичное дерево поиска, ключом в котором является координата x точек.
Каждый узел этого дерева хранит не только точку (или ссылку), но и всё поддерево точек, отсортированных по y

Корень дерева содержит все точки, отсортированные по y.
Левый потомок корня содержит все точки из левого поддерева (те, у которых x меньше медианного), также отсортированные по y.
Правый потомок корня содержит все точки из правого поддерева, отсортированные по y.
Ассоциированная структура: Эта "внутренняя" структура (массив или еще одно дерево поиска, отсортированное по y) и есть ключ к эффективности.

Алгоритм поиска в таком дереве выглядит так:

Найти "узел-разделитель" (Split Node):
Мы спускаемся по основному дереву (по x), используя границы интервала [x1, x2], чтобы найти узел, где пути к x1 и x2 расходятся. Это корень поддерева, которое гарантированно содержит все точки с x в нужном диапазоне.

Рекурсивный обход:
От узла-разделителя мы идем влево по пути к x1.
Каждый раз, когда мы сворачиваем направо (т.е. текущий узел имеет x > x1, и мы идем в левое поддерево), это означает, что правое поддерево текущего узла целиком попадает в интервал по x.
Мы берем ассоциированную структуру этого правого поддерева (отсортированный список по y) и выполняем в ней бинарный поиск по интервалу [y1, y2], добавляя все найденные точки в результат.

Симметрично мы идем от узла-разделителя вправо по пути к x2.
Каждый раз, когда мы сворачиваем налево, его левое поддерево целиком попадает в интервал, и мы обрабатываем его ассоциированную структуру.

Вместо того чтобы проверять каждую точку, мы получаем O(log n) кандидатов (поддеревьев, полностью попадающих в диапазон по x).
В каждом таком кандидате мы тратим O(log n) на бинарный поиск по y.
Итоговая сложность: O(log² n + k), где k — число найденных точек .

-- 24.02.2026, 12:20 --

Литература:
"2D Range Tree Demo" (Университет Мэриленда)
GitHub - CS558/extra-lecture-range-trees
"Foundations of Multidimensional and Metric Data Structures" Ханан Самет (Hanan Samet)
"An implementation of a multidimensional dynamic range tree based on an AVL tree" (Университет Нью-Брансуика)

[B@R5uk]

mathpath, спасибо за подробное объяснение. В дерево диапазонов, кажется, въехал. Я правильно понимаю, что в качестве левой границы всех диапазонов я беру нули, а в качестве правой — координаты тестового вектора? Тогда первый вектор набора, находимый в дереве, является ответом.

[mathpath]

B@R5uk в сообщении #1718920 писал(а):

mathpath, спасибо за подробное объяснение. В дерево диапазонов, кажется, въехал. Я правильно понимаю, что в качестве левой границы всех диапазонов я беру нули, а в качестве правой — координаты тестового вектора? Тогда первый вектор набора, находимый в дереве, является ответом.

Нет
Левая граница — это не ноль.
Если брать левую границу за ноль, а правую за координаты тестового вектора, то область поиска превращается в прямоугольник (или гиперпараллелепипед) от начала координат (0,0) до точки q.
Истинный ближайший сосед может находиться за пределами этого прямоугольника.
Например, если ваш тестовый вектор (100, 1), ближайший сосед может быть в точке (99, 2) (она попадет в прямоугольник), но может быть и в точке (101, 0) (она тоже попадет).

Первый найденный вектор не является ответом (в общем случае).
Если вы просто берете первую попавшуюся точку внутри произвольной области (например, внутри прямоугольника от 0 до q), это не будет гарантированно ближайшим соседом.
В эффективных алгоритмах (как поиск по kd-дереву) мы сначала находим кандидата (обычно спускаясь к листу, содержащему q или ближайший по одному измерению).
Это предположительно ближайший сосед, но не факт.

Как работает поиск ближайшего соседа в kd-дереве (правильно)
Спуск: Мы начинаем с корня и идем вниз, сравнивая координаты тестового вектора q со значениями в узлах (как в бинарном дереве), пока не дойдем до листа.
Точка в этом листе становится текущим лучшим кандидатом.
Обратный ход (Бэктрекинг): Мы поднимаемся обратно к родителям. Для каждого пройденного узла мы проверяем условие: может ли в другой ветке этого узла (которую мы пропустили при спуске) находиться точка, которая ближе, чем текущий кандидат?
Проверка гиперсферой: Мы вычисляем расстояние от q до разделяющей плоскости узла. Если это расстояние меньше, чем текущее лучшее расстояние (best_dist), значит, гиперсфера (область, где гарантированно могут быть точки ближе текущего кандидата) пересекает другую половину пространства. Тогда мы рекурсивно идем в ту ветку.
Обновление: Если в той ветке нашлась точка ближе, обновляем best_dist и кандидата.
Результат: Когда обратный ход закончен, текущий кандидат является ближайшим соседом.

[B@R5uk]

mathpath, так ведь в моей задаче в первом посте надо не ближайший сосед найти, а неперевосходящий.

[rockclimber]

B@R5uk
Посмотрите на картинки в википедии: https://en.wikipedia.org/wiki/R-tree (там для 2 и 3 измерений есть).
Попробуйте сформулировать вашу задачу "графически": у вас есть набор точек в пространстве, каждая точка $a_i$ задает вершину $n$-мерного параллелепипеда, а вектор $b_i$ должен, по сути, помещаться внутри какого-либо параллелепипеда $a_i$.
Начните с двумерного случая. Возможно, так будет нагляднее и проще понять.

[mihaild]

Последний пост mathpath я не понял, откуда тут взялись расстояния?
Базовая идея - очень простая. Строим по первой координате сбалансированное дерево поиска. Во всех его узлах храним аналогичным построенные для соответствующего подмножества деревья по второй координате, в узлах которых храним деревья по третьей и т.д. При поиске ищем все верхние вершины по первой координате, их максимум $\log N$ (с каждого уровня дерева максимум одна), и рекурсивно проверяем деревья по второй и последующей координатам.

[mathpath]

Это классическая проблема доминирования векторов (vector domination problem).
Существуют структуры данных, которые могут отвечать на такие запросы быстрее, чем линейное время.

Для векторов одинаковой размерности d, отношение "поэлементно не превосходит" (a ≤ b) является частичным порядком. Нет полного линейного порядка, но мы можем использовать свойства доминирования.

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

2. Метод многомерных деревьев (KD-деревья)
Для ускорения поиска можно использовать пространственные структуры

3. Метод на основе битовых масок (для малой размерности)
Если размерность невелика (скажем, ≤ 16), можно использовать битовые маски для ускорения

4. Метод "Minimal Skyline" с индексацией
Этот метод особенно эффективен, если векторы распределены неравномерно:


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

[mihaild]

mathpath
Это чем сгенерировано? И зачем?

[zgemm]

B@R5uk в сообщении #1718917 писал(а):

zgemm, я так понимаю, ваш подход работает, когда набор векторов более-менее фиксирован? Или же есть метод эффективно обновлять кластеризацию в случае постоянного их обновления (удаления-добавления)?

подходу век в обед и точного авторства кто первый - я не знаю, а примерно в 1998-1999 я этот подход уже реализовывал :)

Для апдейта кластеризации - все применимо как с классическими структурами деревьев, то есть удаляем и добавляем с логарифмической сложностью но без 100% гарантии точных размеров кластера, но потом редко можно перезапускать оптимизаторы или на части листьев дерева, или на все дерево. В случае очень многомерного вектора (у меня в свое время это было 6-мерное пространство) и довольно статистически равномерно распределенных точек наблюдалась псевдооптимальность - то есть из дерева сколько-то вытащил векторов, сколько-то добавил, а дерево как было более-менее сбалансированное, так и осталось. Не спорю, что программировать такой алгоритм не очень просто, но если сейчас хорошо оркестрировать ИИ, то за вечер или два это все реализуемо.