Техника частичного каскадирования — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ответ на запрос)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 4 участников)
Строка 12: Строка 12:
 
[[Файл:FCT_pic1.jpg|500px|right|thumb|Пример ответа на запрос]]
 
[[Файл:FCT_pic1.jpg|500px|right|thumb|Пример ответа на запрос]]
 
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
 
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
# Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в <tex> i</tex>-ом каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex>, используя [[Целочисленный двоичный поиск|бинарный поиск]]. Так как каталогов <tex> k </tex> штук, то для ответа на запрос понадобится <tex> O(k \log n) </tex> времени. Для хранения всех каталогов понадобится <tex> O(n) </tex> памяти.
+
# Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в <tex> i</tex>-м каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex>, используя [[Целочисленный двоичный поиск|бинарный поиск]]. Так как каталогов <tex> k </tex> штук, то для ответа на запрос понадобится <tex> O(k \log n) </tex> времени. Для хранения всех каталогов понадобится <tex> O(n) </tex> памяти.
# Для второго способа построим сбалансированное бинарное дерево поиска из всех элементов всех каталогов. В каждой вершине дерева со значением будет хранится дополнительно кортеж из <tex> k </tex> элементов {{---}} максимальных представителей каждого каталога меньше либо равных данному значению. Таким образом такая структура будет занимать <tex> O(n) </tex> на дерево поиска и <tex> O(kn) </tex> на дополнительные кортежи.Тогда для ответа на запрос найдем в дереве поиска максимальный ключ меньше либо равный <tex> x </tex> и выведем <tex> k </tex> элементов соответствующего кортежа, итого ответ на запрос производится за <tex> O(\log n + k) </tex>.
+
# Для второго способа построим сбалансированное бинарное дерево поиска из всех элементов всех каталогов. В каждой вершине дерева со значением будет храниться дополнительно кортеж из <tex> k </tex> элементов {{---}} максимальных представителей каждого каталога меньше либо равных данному значению. Таким образом такая структура будет занимать <tex> O(n) </tex> на дерево поиска и <tex> O(kn) </tex> на дополнительные кортежи. Тогда для ответа на запрос найдем в дереве поиска максимальный ключ меньше либо равный <tex> x </tex> и выведем <tex> k </tex> элементов соответствующего кортежа, итого ответ на запрос производится за <tex> O(\log n + k) </tex>.
 
Пример работы второго алгоритма: пусть <tex> C_1 = \{1, 2, 3\}</tex>, <tex> C_2 = \{2, 3, 4\} </tex>, <tex> C_3 = \{1, 3, 4\} </tex> и запрос <tex> x = 2 </tex>.
 
Пример работы второго алгоритма: пусть <tex> C_1 = \{1, 2, 3\}</tex>, <tex> C_2 = \{2, 3, 4\} </tex>, <tex> C_3 = \{1, 3, 4\} </tex> и запрос <tex> x = 2 </tex>.
*Построим кортежи для каждого значения по определению выше.<br><tex> key_1 = 1 \Leftrightarrow p_1 = \{1, \emptyset, 1\} </tex><br><tex> key_2 = 2 \Leftrightarrow p_2 = \{2, 2, 1\} </tex><br><tex> key_3 = 3 \Leftrightarrow p_3 = \{3, 3, 3\} </tex><br><tex> key_4 = 4 \Leftrightarrow p_4 = \{3, 4, 4\} </tex>. <br> <tex> key_i </tex> - значение, которое попадает в дерево поиска, <tex> p_i </tex> кортеж из элементов, который соответствует <tex> key_i </tex>.   
+
*Построим кортежи для каждого значения по определению выше.<br><tex> key_1 = 1 \Leftrightarrow p_1 = \{1, \emptyset, 1\} </tex><br><tex> key_2 = 2 \Leftrightarrow p_2 = \{2, 2, 1\} </tex><br><tex> key_3 = 3 \Leftrightarrow p_3 = \{3, 3, 3\} </tex><br><tex> key_4 = 4 \Leftrightarrow p_4 = \{3, 4, 4\} </tex>. <br> <tex> key_i </tex> {{---}} значение, которое попадает в дерево поиска, <tex> p_i </tex> кортеж из элементов, который соответствует <tex> key_i </tex>.   
 
*Для ответа на запрос найдем в дереве поиска ключ максимальный <tex> key \leqslant x </tex>, для <tex> x = 2 </tex> ключ <tex> key = key_2 = 2 </tex>, тогда в качестве ответа будет выступать кортеж <tex> p_2 </tex>.
 
*Для ответа на запрос найдем в дереве поиска ключ максимальный <tex> key \leqslant x </tex>, для <tex> x = 2 </tex> ключ <tex> key = key_2 = 2 </tex>, тогда в качестве ответа будет выступать кортеж <tex> p_2 </tex>.
 
<br>
 
<br>
Строка 32: Строка 32:
 
<br>
 
<br>
 
Идея данной техники построена на следующем: <br>
 
Идея данной техники построена на следующем: <br>
# Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, в некоторых случаях уменьшит время поиска элемента в следующем каталоге, так как область поиска сожмется. <br>
+
# Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-й каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, в некоторых случаях уменьшит время поиска элемента в следующем каталоге, так как область поиска сожмется. <br>
# Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>
+
# Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-й каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>
  
 
=== Построение ===  
 
=== Построение ===  
Строка 53: Строка 53:
 
<br> <tex> C_4 = \{3, 4, 8, 10, 12\} </tex>
 
<br> <tex> C_4 = \{3, 4, 8, 10, 12\} </tex>
 
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
 
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке. Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета.   
+
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-й строке <tex> j </tex>-я ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке. Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета.   
 
<br>
 
<br>
 
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах:
 
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах:
Строка 67: Строка 67:
 
     '''int''' pointer_in_next_M = 1                <font color=green>// указатель на самый левый элемент каталога M[i + 1], который еще не рассмотрели </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>  
 
     '''int''' pointer_in_M = 1                    <font color=green>// указатель на самый левый элемент каталога M[i], в который будем добавлять элемент </font>  
     '''Node''' last_non_alien = ''null''              <font color=green>// указатель на последний ''неподставной элемент'' для текущей позиции </font>
+
     '''Node''' last_non_alien = <tex> \varnothing </tex>                <font color=green>// указатель на последний неподставной элемент для текущей позиции </font>
     '''Node''' last_alien = ''null''                  <font color=green>// указатель на последний ''подставной элемент'' для текущей позиции</font>
+
     '''Node''' last_alien = <tex> \varnothing </tex>                    <font color=green>// указатель на последний подставной элемент для текущей позиции</font>
 
     '''while''' ''true''
 
     '''while''' ''true''
 
         '''if''' pointer_in_next_M > M[i + 1].size '''and''' pointer_in_C > C[i].size  
 
         '''if''' pointer_in_next_M > M[i + 1].size '''and''' pointer_in_C > C[i].size  
Строка 88: Строка 88:
 
         last_non_alien = M[i][M[i].size]
 
         last_non_alien = M[i][M[i].size]
 
     '''else'''  
 
     '''else'''  
         last_non_alien = ''null''  <font color=green>// теперь last_non_alien указатель на первый справа ''неподставной элемент'' для текущей позиции</font>
+
         last_non_alien = <tex> \varnothing </tex>    <font color=green>// теперь last_non_alien указатель на первый справа неподставной элемент для текущей позиции</font>
 
     '''for''' j = M[i].size - 1 '''downto''' 1       
 
     '''for''' j = M[i].size - 1 '''downto''' 1       
 
         '''if''' M[i][j].is_alien
 
         '''if''' M[i][j].is_alien
Строка 96: Строка 96:
 
             last_non_alien = M[i][j]
 
             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 + ... + 1/p) + n_{k - 1} (1 + 1/2 + 1/4 + ... + 1/(p/2)) + ... + n_1 ) </tex> <tex> = O(2 n_k + 2 n_{k -1} + ... n_1) = O(n) </tex> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.
+
Из построения понятно, что мы тратим <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> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.
  
 
=== Ответ на запрос ===
 
=== Ответ на запрос ===
Строка 115: Строка 115:
 
           cell = cell.right       
 
           cell = cell.right       
 
     '''if''' cell.right <tex> \leqslant </tex> x            <font color=green>// Попытка сдвинуться к большему элементу </font>
 
     '''if''' cell.right <tex> \leqslant </tex> x            <font color=green>// Попытка сдвинуться к большему элементу </font>
           cell = cell.right                             <font color=green>// Замечание: по построению, если мы стоим в ''неподставном элементе'', то при сдвиге вправо мы можем оказаться в элементе любого типа</font>
+
           cell = cell.right       <font color=green>// Замечание: по построению, если мы стоим в ''неподставном элементе'', то при сдвиге вправо мы можем оказаться в элементе любого типа</font>
     '''if''' cell.is_alien                             <font color=green>// Для этого есть проверка </font>
+
     '''if''' cell.is_alien             <font color=green>// Для этого есть проверка </font>
 
           cell = cell.left
 
           cell = cell.left
 
     ans[i] = cell.key
 
     ans[i] = cell.key
Строка 128: Строка 128:
 
|[[Файл:FCT_pic4.jpg|600px|center|thumb|Ответ на запрос <tex> x = 6 </tex>]]
 
|[[Файл:FCT_pic4.jpg|600px|center|thumb|Ответ на запрос <tex> x = 6 </tex>]]
 
|}
 
|}
Рассмотрим, как будет происходить ответ на запрос для <tex> x = 9 </tex> (картинка справа) и для <tex> x = 6 </tex> (картинка слева). Каталоги взяты из примера для построения. Оставлены только ссылки, по которым осуществляется переход, а элементы пронумерованы в порядке обхода.
+
Рассмотрим, как будет происходить ответ на запрос для <tex> x = 9 </tex> (картинка справа) и для <tex> x = 6 </tex> (картинка слева). Каталоги взяты из примера для [[Техника частичного каскадирования#Построение | построения]]. Оставлены только ссылки, по которым осуществляется переход, а элементы пронумерованы в порядке обхода.
 
<br>
 
<br>
  
Строка 142: Строка 142:
 
* [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-12.pdf Fractional Cascading. Bernard Chazelle and Leonidas J. Guibas]
 
* [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 Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах А.П. Пивоваров]
 
* [http://intsys.msu.ru/magazine/archive/v15(1-4)/pivovarov-205-222.pdf Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах А.П. Пивоваров]
*[http://codeforces.com/blog/entry/21892?locale=en Fractional cascading is in fact slow? ifsmirnov's blog]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 19:15, 4 сентября 2022

Определение:
Каталог (англ. catalog) — упорядоченный массив из элементов, на которых введено отношение порядка. В данной статье предполагается, что массив упорядочен по неубыванию.


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


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


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

Пример ответа на запрос

Пусть [math] n = \sum\limits_{i = 1}^k n_i [/math].

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

Пример работы второго алгоритма: пусть [math] C_1 = \{1, 2, 3\}[/math], [math] C_2 = \{2, 3, 4\} [/math], [math] C_3 = \{1, 3, 4\} [/math] и запрос [math] x = 2 [/math].

  • Построим кортежи для каждого значения по определению выше.
    [math] key_1 = 1 \Leftrightarrow p_1 = \{1, \emptyset, 1\} [/math]
    [math] key_2 = 2 \Leftrightarrow p_2 = \{2, 2, 1\} [/math]
    [math] key_3 = 3 \Leftrightarrow p_3 = \{3, 3, 3\} [/math]
    [math] key_4 = 4 \Leftrightarrow p_4 = \{3, 4, 4\} [/math].
    [math] key_i [/math] — значение, которое попадает в дерево поиска, [math] p_i [/math] кортеж из элементов, который соответствует [math] key_i [/math].
  • Для ответа на запрос найдем в дереве поиска ключ максимальный [math] key \leqslant x [/math], для [math] x = 2 [/math] ключ [math] key = key_2 = 2 [/math], тогда в качестве ответа будет выступать кортеж [math] p_2 [/math].


Итого имеем:

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

Решение с помощью техники частичного каскадирования

Как будет показано далее, эта техника берет лучшее от подходов к решению этой задачи, что были рассмотрены выше, а именно она требует [math] O(n) [/math] памяти и [math] O(\log n + k) [/math] времени для ответа на запрос.
Идея данной техники построена на следующем:

  1. Мы можем проводить ссылки из каталога номер [math] i [/math] в [math] (i + 1) [/math]-й каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, в некоторых случаях уменьшит время поиска элемента в следующем каталоге, так как область поиска сожмется.
  2. Мы можем для оптимизации пункта 1 создать модифицированные каталоги [math] M_i [/math], где [math] i [/math]-й каталог будет представлять каталог [math] C_i [/math] слитый с [math] M_{i + 1} [/math]

Построение

Будем называть подставным элементом такой элемент каталога [math] M_i [/math], который пришел из каталога [math] M_{i + 1} [/math]. Сами каталоги [math] M_i [/math] будем называть модифицированными каталогами.

Построение модифицированных каталогов

Первый этап построения:

  • [math] i = k [/math] : Данный каталог не имеет никаких ссылок и равен [math] C_i [/math].
  • [math] i \lt k [/math] : Для построения данного каталога будем сливать каталог [math] C_i [/math] с каждым вторым элементом каталога [math] M_{i + 1} [/math]. Каждый элемент из каталога [math] M_{i + 1} [/math] оснастим ссылкой на позицию, откуда мы его взяли, такие ссылки будет называть ссылками вниз.

Второй этап построения:

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


Рассмотрим на процесс построения на примере.
Пусть дано [math] k = 5 [/math] каталогов:
[math] C_1 = \{1, 3, 6, 7, 11, 12\} [/math]
[math] C_2 = \{4, 9, 10\} [/math]
[math] C_3 = \{1, 2, 7, 8, 11, 12\} [/math]
[math] C_4 = \{3, 4, 8, 10, 12\} [/math]
[math] C_5 = \{1, 2, 4, 6, 9\} [/math]
Для наглядности заведем таблицу, где в [math]i[/math]-й строке [math] j [/math]-я ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге [math] C_i [/math]. Тогда результатом построения будет таблица, которая представлена на рисунке. Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета.
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах:

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                     // указатель на самый левый элемент каталога C[i], который еще не рассмотрели 
    int pointer_in_next_M = 1                // указатель на самый левый элемент каталога M[i + 1], который еще не рассмотрели 
    int pointer_in_M = 1                     // указатель на самый левый элемент каталога M[i], в который будем добавлять элемент  
    Node last_non_alien = [math] \varnothing [/math]                 // указатель на последний неподставной элемент для текущей позиции 
    Node last_alien = [math] \varnothing [/math]                     // указатель на последний подставной элемент для текущей позиции
    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] [math] \geqslant [/math] 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 = [math] \varnothing [/math]     // теперь last_non_alien указатель на первый справа неподставной элемент для текущей позиции
    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]

Из построения понятно, что мы тратим [math] O(n_k) [/math] на построение последнего каталога, [math] O(n_{k-1} + n_k / 2) [/math] на построение предпоследнего и т.д. Пусть [math] p = 2^{n - 1} [/math]. Тогда получаем оценку [math] 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 ) [/math] [math] = O(2 n_k + 2 n_{k -1} + \dots n_1) = O(n) [/math] памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.

Ответ на запрос

  • В первом каталоге ответ на запрос найдем с помощью бинарного поиска по [math] M_1 [/math]. Пусть ответом для этого каталога будет ячейка [math] cell [/math], тогда если [math] cell [/math] — подставная вершина, то перейдем по ссылке влево.
  • Проитерируемся по оставшимся каталогам.
    • Для того, чтобы перейти в новый модифицированный каталог мы перейдем из [math] cell [/math] по ссылке влево, чтобы попасть в подставную вершину, а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог.
    • Если теперь [math] cell [/math] — неподставная вершина, то нам достаточно рассмотреть двух ее соседей справа в [math] C_i [/math], так как [math] cell.key \leqslant x [/math], а каждая вторая ячейка из [math] M_i [/math] попадает в [math] M_{i - 1} [/math], т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но этого не случилось.
    • Обновив [math] cell [/math] максимальным из подходящих значений нужно проверить, является ли она подставным элементом, если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.
Node cell = binary_search(M[1], x)
if cell.is_alien 
    cell = cell.left
ans[1] = cell.key;                // ans[i] - ответ на текущий запрос для каталога С[i]  
for i = 2 to k
    cell = cell.left.down         
    if cell.right [math] \leqslant [/math] x            // Попытка сдвинуться к большему элементу 
         cell = cell.right      
    if cell.right [math] \leqslant [/math] x            // Попытка сдвинуться к большему элементу 
         cell = cell.right       // Замечание: по построению, если мы стоим в неподставном элементе, то при сдвиге вправо мы можем оказаться в элементе любого типа
    if cell.is_alien             // Для этого есть проверка 
         cell = cell.left
    ans[i] = cell.key

Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один бинарный поиск, что требует [math] O(\log n) [/math] времени, после чего необходимо [math] O(k) [/math] времени, чтобы ответить на запрос для всех остальных каталогов. Суммарное время работы [math] O(\log n + k) [/math].

Примеры ответа на запрос

Ответ на запрос [math] x = 9 [/math]
Ответ на запрос [math] x = 6 [/math]

Рассмотрим, как будет происходить ответ на запрос для [math] x = 9 [/math] (картинка справа) и для [math] x = 6 [/math] (картинка слева). Каталоги взяты из примера для построения. Оставлены только ссылки, по которым осуществляется переход, а элементы пронумерованы в порядке обхода.

Дополнительно

Данная техника может использоваться для ускорения некоторых алгоритмов, где требуется ответить на запрос на отрезке [math] [L, R] [/math], где [math] L, R \in R^n, n \in \mathbb N [/math]. Однако иногда наблюдается замедление[1].

См. также

Примечания

Ссылки