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

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

Алгоритм

Пусть есть уже построенное дерево отрезков и идет запрос на отрезке [math][a .. b][/math].

Пример дерева отрезков

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

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

Пусть [math]l[/math], [math]r[/math] — это левая и правая границы отрезков, за которые "отвечает" наша вершина, причем левые границы обоих отрезков - включительно, а правые - нет. В дальнейшем будем называть подобную структуру полуинтвервалом.

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

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

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

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

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

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

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

Замечание:

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

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

Пример

Рассмотрим данный алгоритм на примере задачи RSQ(запрос суммы на отрезке).

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

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

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

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

• листья [math]5[/math] и [math]0[/math] не пересекается с полуинтервалом [math][1 .. 5)[/math] => возвращаем нулевое значение, листья [math]4[/math] и [math]1[/math] целиков внутри [math][1 .. 5)[/math] => возвращаем значения в этих листьях.

Реализация

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

 int get_sum (int node, int a, int b)
 {
       // Рассматриваем в реализаций полуинтервалы 
       
       l = tree[node].left;
       r = tree[node].right; 
       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 :: Дерево отрезков

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

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