Техника частичного каскадирования

Техника частичного каскадирования (англ. fractional cascading technique) — это способ организации структуры данных, который предназначен для быстрого итеративного поиска в [math] k [/math] каталогах.

Задача:

Дано [math] k [/math] каталогов [math] C_i [/math], каталог [math]i[/math] представляет собой упорядоченный массив размера [math] n_i [/math]. Поступают запросы, которые представляют собой один элемент [math] x [/math]. Требуется для каждого запроса определить в каждом каталоге элемент меньше либо равный [math] x [/math].

Различные подходы к решению

Пусть [math] n = \sum\limits_{i = 1}^k n_i [/math].
1) Пусть пришел запрос [math] x [/math]. Пробежимся по всем каталогам. Пусть мы находимся в [math] i[/math]-ом каталоге, тогда мы можем ответить на запрос для данного каталога за [math] O(\log n_i) [/math] используя бинарный поиск. Так как каталогов [math] k [/math] штук, то в итоге мы обработаем запрос за [math] O(k \log n) [/math]. Для хранения всех каталогов понадобится [math] \Theta(n) [/math] памяти.