Изменения

1) Пусть пришел Для ответа на запрос <tex> x </tex>. Пробежимся по всем каталогампоследовательно посетим все каталоги. Пусть мы находимся в <tex> i</tex>-ом каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex> используя бинарный поиск. Так как каталогов <tex> k </tex> штук, то в итоге мы обработаем запрос за <tex> O(k \log n) </tex>. Для хранения всех каталогов понадобится <tex> \Theta(n) </tex> памяти.

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