Изменения

{{Определение|definition='''Техника частичного каскадирования''' (англ. ''fractional cascading technique'') {{---}} это способ организации структуры данных, который предназначен для быстрого итеративного поиска в <tex> k </tex> каталогах.}} 

[[Файл:FCT_pic2.jpg|600px|left|thumb|Построение модифицированных каталогов без ссылок из подставных элементов]]

<br> В каждом ''модифицированном каталоге'' для каждого элемента заведем две ссылки. Для ''неподставных элементов'' это будут ссылки на минимальный максимальный''подставной элемент'' больше меньше текущего и на максимальный минимальный любого типа меньше больше текущего. И наоборот, если Если ''элемент подставной'', то ссылки будут на минимальный ''неподставной элемент любого типа " больше текущего и на максимальный ''неподставной элемент'' меньше текущего. Назовем их ссылками влево и вправо.

В первом каталоге <tex> C_1 </tex> ответ на запрос найдем с помощью бинарного поиска по <tex> C_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый модифицированный каталог мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в подставную вершину, а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> - неподставная вершина, то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранее.Обновив cell осталось проверить, что она не