112
правок
Изменения
Добавлены примеры ответа на запросы
Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один [[Целочисленный двоичный поиск|бинарный поиск]], что требует <tex> O(\log n) </tex> времени, после чего необходимо <tex> O(k) </tex> времени, чтобы ответить на запрос для всех остальных каталогов. Суммарное время работы <tex> O(\log n + k) </tex>.
<br>
{| border="0" cellpadding="5" cellspacing="0" center
|[[Файл:FCT_pic3.jpg|500px|center|thumb|Ответ на запрос x = 9]]
|[[Файл:FCT_pic3.jpg|500px|center|thumb|Ответ на запрос x = 6]]
|}
Рассмотрим как будет происходить ответ на запрос для x = 9 (картинка справа) и для x = 6 (картинка слева). Каталоги взяты из примера для построения. Оставлены только ссылки, по которым осуществляется переход, а элементы пронумерованы в порядке обхода.
<br>
==Дополнительно==
Данная техника может использоваться для ускорения некоторых алгоритмов, где требуется ответить на запрос на отрезке [L, R], где <tex> L, R \in R^n, n \in \mathbb N </tex>. Однако иногда наблюдается замедление, о чем можно почитать [http://codeforces.com/blog/entry/21892?locale=en тут].
