Изменения
Исправлены пункты: 3_1, 3_2, 3_3, 3_4, 3_5, 3_9, 3_10
[[Файл:FCT_pic1.jpg|500px|right|thumb|Пример ответа на запрос]]
Пусть <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> \ThetaO(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> 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>.
! Тип подхода к решению !! Необходимая память !! Время ответа на один запрос
|-
| <center><tex> k </tex> [[Целочисленный двоичный поиск|бинарных поисков]] </center> || <center><tex> \ThetaO(n) </tex></center> || <center><tex> O(k \log n) </tex></center>
|-
| <center>Построение [[Поисковые структуры данных|бинарного дерева поиска]] с кортежами</center> || <center><tex> O(kn) </tex></center> || <center><tex> O(\log n + k) </tex></center>
|}
<br> <tex> C_4 = \{3, 4, 8, 10, 12\} </tex>
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке.Для упрощения рисунка ссылки вправо из неподставных элементов не были отображены, их следует воспринимать как следующий справа от рассматриваемого элемент в ряду таблицы любого цвета.
<br>
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах:
'''Node''' left, right, down
'''bool''' is_alien
=== Ответ на запрос ===
*В первом каталоге ответ на запрос найдем с помощью [[Целочисленный двоичный поиск|бинарного поиска]] по <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> максимальным из подходящих значений нужно проверить, является ли она подставным элементом, если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.
