Изменения

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

<br>1) # Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в <tex> i</tex>-ом каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex>, используя [[Целочисленный двоичный поиск|бинарный поиск]]. Так как каталогов <tex> k </tex> штук, то для ответа на запрос понадобится <tex> O(k \log n) </tex> времени. Для хранения всех каталогов понадобится <tex> \Theta(n) </tex> памяти.<br>2) # Для второго способа построим [[Поисковые структуры данных|сбалансированное бинарное дерево поиска]] из всех элементов всех каталогов. В каждой вершине дерева со значением будет хранится дополнительно кортеж из <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>.*Построим кортежи для каждого значения по определению выше.<br><tex> key_1 = 1 \Leftrightarrow p_1 = \{1, null\emptyset, 1\} </tex><br><tex> key_2 = 2 \Leftrightarrow p_2 = \{2, 12, 1\} </tex><br><tex> key_3 = 3 \Leftrightarrow p_3 = \{3, 23, 23\} </tex><br><tex> key_4 = 4 \Leftrightarrow p_4 = \{3, 34, 34\} </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>.

* 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>

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

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

struct node '''Node''': '''element ''' key node '''Node''' left, right, down '''bool ''' is_alien

'''for''' i = k - 1 '''todownto''' 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 '''Node''' last_non_alien = NULL <font color=green>// указатель на последний ''неподставной элемент'' для текущей позиции </font> node '''Node''' last_alien = NULL <font color=green>// указатель на последний ''подставной элемент'' для текущей позиции</font>

'''if''' (pointer_in_next_M > M[i + 1].size || M[i + 1][pointer_in_next_M] <tex> \geqslant </tex>= C[i][pointer_in_C])

*В первом каталоге ответ на запрос найдем с помощью [[Целочисленный двоичный поиск|бинарного поиска]] по <tex> 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 '''Node''' cell = binary_search(M[1], x)

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

'''if''' (cell.right <= tex> \leqslant </tex> x) <font color=green>// Попытка сдвинуться к большему элементу </font>

'''if''' (cell.right <= tex> \leqslant </tex> x) <font color=green>// Попытка сдвинуться к большему элементу </font>

|[[Файл:FCT_pic3.jpg|500px|center|thumb|Ответ на запрос <tex> x = 9</tex>]]|[[Файл:FCT_pic4.jpg|500px|center|thumb|Ответ на запрос <tex> x = 6</tex>]]

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

===Дополнительно===Данная техника может использоваться для ускорения некоторых алгоритмов, где требуется ответить на запрос на отрезке <tex> [L, R]</tex>, где <tex> L, R \in R^n, n \in \mathbb N </tex>. Однако иногда наблюдается замедление, о чем можно почитать [http://codeforces.com/blog/entry/21892?locale=en тут].