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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
Строка 45: Строка 45:
  
 
==Реализация==
 
==Реализация==
 +
Рассмотрим реализацию рассматриваемой выше задачи RSQ.
 
<code>
 
<code>
  
Строка 50: Строка 51:
 
   {
 
   {
 
         l = tree[node].left;
 
         l = tree[node].left;
         r = tree[node].right;
+
         r = tree[node].right;  
         if [l, r] <tex>\bigcap</tex> [a, b] == <tex> \varnothing</tex>
+
        // [l, r)
 +
         if [l, r) <tex>\bigcap</tex> [a, b) == <tex> \varnothing</tex>
 
             return 0;
 
             return 0;
         if [l, r] == [a, b]
+
         if [l, r) == [a, b)
 
             return tree[node];
 
             return tree[node];
 
         int m = (l + r) / 2;
 
         int m = (l + r) / 2;
 
         return get_sum (node * 2 + 1, a, min(b, m))
 
         return get_sum (node * 2 + 1, a, min(b, m))
             + get_sum (node * 2 + 2, max(a, m + 1), b);
+
             + get_sum (node * 2 + 2, max(a, m), b);
 
   }  
 
   }  
 
</code>
 
</code>

Версия 22:10, 28 апреля 2012

Данная рекурсивная операция позволяет выполнять запросы на дереве отрезков, причем алгоритм запускается от корня и рекурсивно идет сверху вниз.

Алгоритм

Пример

Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке), то есть пусть есть уже построенное дерево отрезков построенное дерево отрезков и задача найти сумму на отрезке [math][a .. b][/math].

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

Будем передавать в качестве параметров рекурсий следующие переменные:

  • [math]node[/math] — номер(в массиве с деревом отрезков) текущей вершины дерева.
  • [math]l[/math], [math]r[/math] — левая и правая границы отрезков, за которые "отвечает" наша вершина.
  • [math]a[/math], [math]b[/math] — левая и правая границы запрашиваемого отрезка.

Запустим рекурсивную процедуру от всего отрезка(то есть от корневой вершины).

Для текущего состояния проверяем следующие условия :

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

Например: текущий [math][1..2][/math], а искомый [math][3 .. 4][/math];

  • Текущий отрезок совпадает, то возвращаем значение в текущей вершине.

Например: текущий и искомый [math][2..3][/math];

  • Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом сумма на текущем отрезке равна сумме результатов функций, запущенных от детей.

Замечание:

При передаче новых параметров следует изменять не только границы, за которые отвечает текущая вершина, но и границы запрашиваемого отрезка, чтобы на последующих шагах произошло полное совпадение отрезков.

Так как каждый отрезок разбивается не более, чем на [math]O(\log n)[/math] отрезков (поскольку на каждом уровне дерева может быть не более двух отрезков из разбиения, а всего уровней [math]\log n[/math] ), то данная реализация выполняется за [math]O(\log n)[/math].

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

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

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


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


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

Реализация

Рассмотрим реализацию рассматриваемой выше задачи RSQ.

 int get_sum (int node, int a, int b)
 {
       l = tree[node].left;
       r = tree[node].right; 
       // [l, r) 
       if [l, r) [math]\bigcap[/math] [a, b) == [math] \varnothing[/math]
           return 0;
       if [l, r) == [a, b)
           return tree[node];
       int m = (l + r) / 2;
       return get_sum (node * 2 + 1, a, min(b, m))
           + get_sum (node * 2 + 2, max(a, m), b);
 } 

Ссылки

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

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

Визуализатор дерева отрезков