Линейный по памяти непереборный алгоритм решения двумерной задачи интервального поиска

Предлагается алгоритм решения двумерной задачи интервального поиска, который имеет следующие характеристики: объем требуемой памяти порядка $k$, среднее время поиска (без учета времени перечисления ответа) порядка $\sqrt{k}$, где $k$ — размер исходной базы данных.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 01–01–00748.