112
правок
Изменения
Добавлена тема "См. также" и "Дополнительно", исправлены пункты 4
Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один бинарный поиск, что требует <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 тут].
==См. также==
[[Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)]]
== Ссылки ==
* [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-12.pdf Fractional Cascading. Bernard Chazelle and Leonidas J. Guibas]
