112
правок
Изменения
м
Нет описания правки
<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>, построим кортежи для каждого значения по определению выше.<br><tex> key_1 = 1 \Leftrightarrow p_1 = \{1, 0null, 1\} </tex><br><tex> key_2 = 2 \Leftrightarrow p_2 = \{2, 1, 1\} </tex><br><tex> key_3 = 3 \Leftrightarrow p_3 = \{3, 2, 2\} </tex><br><tex> key_4 = 4 \Leftrightarrow p_4 = \{3, 3, 3\} </tex>. <br> <tex> key_i </tex> - значение, которое попадает в дерево поиска, <tex> p_i </tex> кортеж из позиций, который соответствует <tex> key_i </tex>.
<br>
Итого имеем:
