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

Техника частичного каскадирования (англ. 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] памяти.
2) Для второго способа построим сбалансированное бинарное дерево поиска их всех элементов всех каталогов. В каждой вершине дерева будет хранится дополнительно кортеж из [math] k [/math] элементов - максимальных представителей каталогов меньше либо равных ключу вершины. Таким образом такая структура будет занимать [math] O(n) [/math] на дерево поиска и [math] O(kn) [/math] на дополнительные кортежи.Тогда для ответа на запрос [math] x [/math] найдем в дереве поиска максимальный ключ меньше либо равный [math] x [/math] и выведем [math] k [/math] элементов соответствующего кортежа, итого ответ на запрос производится за [math] O(\log n + k) [/math].

Итого имеем

Тип подхода к решению	Необходимая память	Время ответа на один запрос
[math] k [/math] бинарных поисков	[math] \Theta(n) [/math]	[math] O(k \log n) [/math]
Построение бинарного дерева поиска с кортежами	[math] O(kn) [/math]	[math] O(\log n + k) [/math]