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

[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 на запрос.
Для большой размерности придётся мириться с почти линейным временем или использовать приближённые методы.