Изменения

# Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в <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>.

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

<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой й строке <tex> j </tex>-ая я ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке. Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета.

'''Node''' last_non_alien = ''null'' <tex> \varnothing </tex> <font color=green>// указатель на последний ''неподставной элемент'' для текущей позиции </font> '''Node''' last_alien = ''null'' <tex> \varnothing </tex> <font color=green>// указатель на последний ''подставной элемент'' для текущей позиции</font>

last_non_alien = '''if''' '''not''' M[i][M[i].size].is_alien ? last_non_alien = M[i][M[i].size] : '''else'null'' last_non_alien = <tex> \varnothing </tex> <font color=green>// теперь это last_non_alien указатель на первый справа ''неподставной элемент'' для текущей позиции</font>

Из построения понятно, что мы тратим <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> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.

ans[1] = cell.key; <font color=green>// ans[i] - ответ на текущий запрос для каталога С[i] </font>

cell = cell.left.down '''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> '''if''' cell.is_alien <font color=green>// Для этого есть проверка </font>

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