Изменения

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

472 байта добавлено, 23:05, 16 мая 2011

Ж

Будем рассматривать запрос на примере задачи RSQ(запрос суммы)

[[Файл:123.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]

~~Если запрашиваемый отрезок не пересекается с рассматриваемым отрезком, возвращаем нейтральный элемент.~~

~~Если запрашиваемый отразив совпадает с запрашиваемый, возвращаем значение в вершине.~~

~~Иначе считаем для подотрезков рекурсивно, комбинируем ответ и возвращаем значение.~~

Пусть есть дерево отрезков и задача найти сумму на отрезке [a .. b], далее искомый.

Запустим рекурсивную процедуру от всего отрезка.

Проверять будем два условия :

1)если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.

Например:

текущий [1..2], а искомый [3 .. 4];

2)текущий отрезок целиком внутри, то возвращаем значение в вершине.

Например:

текущий [2..3], а искомый [1 .. 4];

Далее переходим к рекурсивным вызовам

результат функции от текущего отрезка и искомого = сумма результатов от детей текущего отрезка и искомого.

==Пример==

228

правок