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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ж)
(Алгоритм)
Строка 9: Строка 9:
 
Проверять будем два условия :
 
Проверять будем два условия :
  
1)если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.
+
*если текущий отрезок не пересекается с искомым, то возвращаем нулевое значение.
 
Например:
 
Например:
  
 
текущий [1..2], а искомый [3 .. 4];
 
текущий [1..2], а искомый [3 .. 4];
  
2)текущий отрезок целиком внутри, то возвращаем значение в вершине.
+
*текущий отрезок целиком внутри, то возвращаем значение в вершине.
 
Например:
 
Например:
  
Строка 20: Строка 20:
  
 
Далее переходим к рекурсивным вызовам
 
Далее переходим к рекурсивным вызовам
    результат функции от текущего отрезка и искомого = сумма результатов от детей текущего отрезка и искомого.
+
результат функции от текущего отрезка и искомого = сумма результатов от детей текущего отрезка и искомого.
  
 
==Пример==
 
==Пример==

Версия 23:11, 16 мая 2011

Алгоритм

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

Пример дерева отрезков для вычисления сумм

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

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

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

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

Например:

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

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

Например:

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

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

Пример

Дерево отрезков

Рассмотрим работу программы на дереве отрезков для элементов [1 .. 8]. Пусть запрашиваемая сумма - это отрезок [2 .. 5].

1)Текущий отрезок [1 .. 8], он больше [2 .. 5] => переходим по рекурсивным вызовам на [1 .. 4] и [5 .. 8]


2)[1 .. 4] выходит за границы [2 .. 5], [5 .. 8] выходит за границы [2 .. 5] => переходим по рекурсивным вызовам на [1 .. 2], [3 .. 4] и [5 .. 6], [7 .. 8].


3)[1 .. 2] выходит за границы [2 .. 5] => переходим в листья 1, 2; [3 .. 4] целиком внутри [2 .. 5] => возвращаем значение в [3 .. 4]; [7 .. 8] не пересекается с [2 .. 5] => возвращаем нулевое значение, [5 .. 6] выходит за границы [2 .. 5] => переходим к листьям 5 и 6


4)лист 6 не пересекается с отрезком [2 .. 5] => возвращаем нулевое значение, лист 5 целиков внутри [2 .. 5] => возвращаем значение в листе 5.

Реализация

 int sum (int v, int tl, int tr, int l, int r)
 {
       if ([l,r] не пересекается с [tl, tr])
           return 0;
       if (l == tl && r == 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);
 } 

Ссылки

- MAXimal :: algo :: Дерево отрезков

- Дерево отрезков — Википедия