Изменения

Перейти к: навигация, поиск

Реализация запроса в дереве отрезков сверху

177 байт добавлено, 22:54, 28 апреля 2012
Пример
Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке).
Рассмотрим работу алгоритма для вычисления суммы При этом сумма на текущем отрезке(в случае вызова рекурсий от детей) равна сумме результатов выполнения операций на этих детях.  Пусть дерево содержит 8 листьев и запрашиваемая сумма - это отрезок <tex>[1 .. 4]</tex>( полуинтервал <tex>[1 .. 5)</tex>). Рассмотрим данную рекурсию:
*Текущий полуинтервал <tex>[0 .. 8)</tex>, он больше <tex>[1 .. 5)</tex> => переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>
333
правки

Навигация