112
правок
Изменения
Добавлены ссылки на "бинарный поиск" и "дерево поиска", исправлен пункт 6
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
<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>.
<br> <br>
Итого имеем:
! Тип подхода к решению !! Необходимая память !! Время ответа на один запрос
|-
| <center><tex> k </tex> [[Целочисленный двоичный поиск|бинарных поисков ]] </center> || <center><tex> \Theta(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>
|}
=== Ответ на запрос ===
*В первом каталоге ответ на запрос найдем с помощью [[Целочисленный двоичный поиск|бинарного поиска ]] по <tex> M_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>, тогда если cell {{---}} ''подставная вершина'', то перейдем по ссылке влево.
*Проитерируемся по оставшимся каталогам.
**Для того, чтобы перейти в новый ''модифицированный каталог'' мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в ''подставную вершину'', а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог.
ans[i] = cell.key
Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один [[Целочисленный двоичный поиск|бинарный поиск]], что требует <tex> O(\log n) </tex> времени, после чего необходимо <tex> O(k) </tex> времени, чтобы ответить на запрос для всех остальных каталогов. Суммарное время работы <tex> O(\log n + k) </tex>.
==Дополнительно==
Данная техника может использоваться для ускорения некоторых алгоритмов, где требуется ответить на запрос на отрезке [L, R], где <tex> L, R \in R^n, n \in \mathbb N </tex>. Однако иногда наблюдается замедление, о чем можно почитать [http://codeforces.com/blog/entry/21892?locale=en тут].
