Изменения

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

| <center><tex> k </tex> [[Целочисленный двоичный поиск|бинарных поисков ]] </center> || <center><tex> \ThetaO(n) </tex></center> || <center><tex> O(k \log n) </tex></center>

1) # Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый й каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поискаэлемента в следующем каталоге, так как область поиска сожмется. <br>2) # Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый й каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex> === Построение === Будем называть подставным элементом такой элемент каталога <tex> M_i </tex>, который пришел из каталога <tex> M_{i + 1} </tex>. Сами каталоги <brtex> M_i </tex>будем называть модифицированными каталогами.

=== Построение ===Рассмотрим подробнее построение каталогов <tex> M_i </tex>. Введем определения: {{Определение|definition='''Подставной элемент''' {{---}} элемент каталога <tex> M_i </tex>, который пришел из каталога <tex> M_{i + 1} </tex>. А также каталоги <tex> M_i </tex> будем называть '''модифицированными каталогами'''.}}[[Файл:FCT_pic2.jpg|600px800px|left|thumb|Построение модифицированных каталогов без ссылок из подставных элементов]]<br>'''Первый этап построения''':<br> *<tex> i = k </tex> : Данный каталог не имеет никаких ссылок и равен <tex> C_i </tex>.<br> *<tex> i < k </tex> : Для построения данного каталога будем сливать каталог <tex> C_i </tex> с каждым вторым элементом каталога <tex> M_{i + 1} </tex>. Каждый элемент из каталога <tex> M_{i + 1} </tex> оснастим ссылкой на позицию, откуда мы его взяли, такие ссылки будет называть ссылками вниз.

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

<br> Пусть дано <tex> k = 5 </tex> каталогов :

<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой й строке <tex> j </tex>-ая я ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке (без . Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета. <br>Из-за необходимости хранения ссылок из будет удобно завести структуру для хранения элементов в модифицированных каталогах: '''struct''' Node: '''T''' key '''Node''' left, right, down '''bool''' is_alien  Псевдокод построения модифицированных каталогов: M[k] = C[k] '''for''' i = k - 1 '''downto''' 1 '''int''' pointer_in_C = 1 <font color=green>// указатель на самый левый элемент каталога C[i], который еще не рассмотрели </font> '''int''' pointer_in_next_M = 1 <font color=green>// указатель на самый левый элемент каталога M[i + 1], который еще не рассмотрели </font> '''int''' pointer_in_M = 1 <font color=green>// указатель на самый левый элемент каталога M[i], в который будем добавлять элемент </font> '''Node''' last_non_alien = <tex> \varnothing </tex> <font color=green>// указатель на последний неподставной элемент для текущей позиции </font> '''Node''' last_alien = <tex> \varnothing </tex> <font color=green>// указатель на последний подставной элемент для текущей позиции</font> '''while''' ''true'' '''if''' pointer_in_next_M > M[i + 1].size '''and''' pointer_in_C > C[i].size '''break''' '''if''' pointer_in_next_M > M[i + 1].size '''or''' M[i + 1][pointer_in_next_M] <tex> \geqslant </tex> C[i][pointer_in_C] M[i][pointer_in_M].key = C[i][pointer_in_C].key M[i][pointer_in_M].left= last_alien last_non_alien = M[i][pointer_in_M] pointer_in_C++ '''else''' M[i][pointer_in_M].key = M[i + 1][pointer_in_next_M].key M[i][pointer_in_M].down = M[i + 1][pointer_in_next_M] M[i][pointer_in_M].is_alien = ''true'' M[i][pointer_in_M].left = last_non_alien last_alien = M[i][pointer_in_M] pointer_in_next_M += 2 pointer_in_M++ '''if''' '''not''' M[i][M[i].size].is_alien last_non_alien = M[i][M[i].size] '''else''' last_non_alien = <tex> \varnothing </tex> <font color=green>// теперь last_non_alien указатель на первый справа неподставной элемент для текущей позиции</font> '''for''' j = M[i].size - 1 '''downto''' 1 '''if''' M[i][j].is_alien M[i][j].right = last_non_alien '''else'подставных элементов'' M[i][j].right = M[i][j + 1] last_non_alien = M[i][j] Из построения понятно, что мы тратим <tex> O(n_k) </tex> на построение последнего каталога, <tex> O(n_{k-1} + n_k / 2) </tex> на построение предпоследнего и т.д. Пусть <tex> p = 2^{n - 1} </tex>. Тогда получаем оценку <tex> O(n_k (1 + 1/2 + 1/4 + \dots + 1/p) + n_{k - 1} (1 + 1/2 + 1/4 + \dots + 1/(p/2)) + \dots + n_1 ) </tex> <tex> = O(2 n_k + 2 n_{k -1} + \dots n_1) = O(n)</tex> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.

*В первом каталоге <tex> C_1 </tex> ответ на запрос найдем с помощью [[Целочисленный двоичный поиск|бинарного поиска ]] по <tex> C_1 M_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>, тогда если <tex> cell </tex> {{---}} подставная вершина, то перейдем по ссылке влево. Далее проитерируемся *Проитерируемся по оставшимся каталогам. **Для того, чтобы перейти в новый модифицированный каталог мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в подставную вершину, а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. **Если теперь <tex> cell </tex> {{--- }} неподставная вершина, то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < \leqslant x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранееи перешли мы вниз по ней, но этого не случилось.**Обновив <tex> cell </tex> максимальным из подходящих значений нужно проверить, является ли она подставным элементом, если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.  '''Node''' cell = binary_search(M[1], x) '''if''' cell.is_alien cell = cell.left ans[1] = cell.key; <font color=green>// ans[i] - ответ на текущий запрос для каталога С[i] </font> '''for''' i = 2 '''to''' k cell = cell.left.down '''if''' cell.right <tex> \leqslant </tex> x <font color=green>// Попытка сдвинуться к большему элементу </font> cell = cell.right '''if''' cell.right <tex> \leqslant </tex> x <font color=green>// Попытка сдвинуться к большему элементу </font> cell = cell.right <font color=green>// Замечание: по построению, если мы стоим в ''неподставном элементе'', то при сдвиге вправо мы можем оказаться в элементе любого типа</font> '''if''' cell.is_alien <font color=green>// Для этого есть проверка </font> cell = cell.left ans[i] = cell.key Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один [[Целочисленный двоичный поиск|бинарный поиск]], что требует <tex> O(\log n) </tex> времени, после чего необходимо <tex> O(k) </tex> времени, чтобы ответить на запрос для всех остальных каталогов. Суммарное время работы <tex> O(\log n + k) </tex>.<br>  ====Примеры ответа на запрос===={| border="0" cellpadding="5" cellspacing="0" center|[[Файл:FCT_pic3.jpg|600px|center|thumb|Ответ на запрос <tex> x = 9 </tex>]]|[[Файл:FCT_pic4.jpg|600px|center|thumb|Ответ на запрос <tex> x = 6 </tex>]]|}Рассмотрим, как будет происходить ответ на запрос для <tex> x = 9 </tex> (картинка справа) и для <tex> x = 6 </tex> (картинка слева). Каталоги взяты из примера для [[Техника частичного каскадирования#Построение | построения]]. Оставлены только ссылки, по которым осуществляется переход, а элементы пронумерованы в порядке обхода.<br> ===Дополнительно===Данная техника может использоваться для ускорения некоторых алгоритмов, где требуется ответить на запрос на отрезке <tex> [L, R] </tex>, где <tex> L, R \in R^n, n \in \mathbb N </tex>. Однако иногда наблюдается замедление<ref>[http://codeforces.com/blog/entry/21892?locale=en Fractional cascading is in fact slow? ifsmirnov's blog]</ref>. ==См. также==*[[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]]*[[Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)]]== Примечания ==<references />== Ссылки ==* [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-12.pdf Fractional Cascading. Bernard Chazelle and Leonidas J. Guibas]* [http://intsys.msu.ru/magazine/archive/v15(1-4)/pivovarov-205-222.pdf Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах А.П.Пивоваров] [[Категория: Алгоритмы и структуры данных]][[Категория: Структуры данных]]