Реализация запроса в дереве отрезков сверху
Содержание
Алгоритм
Будем рассматривать запрос на примере задачи RSQ(запрос суммы)
Пусть есть дерево отрезков и задача найти сумму на отрезке
, далее искомый.Запустим рекурсивную процедуру от всего отрезка.
Проверять будем два условия :
- если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.
Например:
текущий
, а искомый ;- текущий отрезок совпадает, то возвращаем значение в вершине.
Например:
текущий и искомый
;Далее переходим к рекурсивным вызовам результат функции от текущего отрезка и искомого = сумма результатов от детей текущего отрезка и искомого.
Пример
Рассмотрим работу программы на дереве отрезков для элементов
. Пусть запрашиваемая сумма - это отрезок .- Текущий отрезок , он больше => переходим по рекурсивным вызовам на и
- выходит за границы , выходит за границы => переходим по рекурсивным вызовам на , и , .
- выходит за границы => переходим в листья 1, 2; целиком внутри => возвращаем значение в ;
не пересекается с => возвращаем нулевое значение, выходит за границы => переходим к листьям 5 и 6
- лист 6 не пересекается с отрезком => возвращаем нулевое значение, лист 5 целиков внутри => возвращаем значение в листе 5.
Реализация
int sum (int v, int tl, int tr, int l, int r) { if ([l,r][tl, tr]) = return 0; if ([l,r] [tl, tr]) return t[v]; int tm = (tl + tr) / 2; return sum (v*2, tl, tm, l, min(r,tm)) + sum (v*2+1, tm+1, tr, max(l,tm+1), r); }