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

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

Алгоритм

Замечание. Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая - нет).

Пусть есть уже построенное дерево отрезков и идет запрос на полуинтервале [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..3)[/math], а искомый [math][2..4)[/math];

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

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

Пример

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

При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операций на этих детях.

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

Рассмотрим данный алгоритм на определенных глубинах рекурсии:

• Текущий полуинтервал [math][0 .. 8)[/math] пересекается с [math][1 .. 5) \Rightarrow[/math] переходим по рекурсивным вызовам на [math][0 .. 4)[/math] и [math][4 .. 8)[/math]

• [math][0 .. 4)[/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][4 .. 6)[/math] пересекаются с [math][1 .. 5) \Rightarrow [/math] переходим в листья [math]0, 1, 4, 5 [/math]; [math][2 .. 4) [/math] полностью лежит внутри [math][1 .. 5) \Rightarrow [/math] возвращаем сумму на этом отрезке; а [math][6 .. 8)[/math] не пересекается с [math][1 .. 5) \Rightarrow [/math] возвращаем нулевое значение.

• Листья [math]1, 4[/math] лежат в запрашиваемом интервале [math]\Rightarrow [/math] возвращаем значения в них, в то время как листья [math]0, 5[/math] лежат вне [math][1 .. 5) \Rightarrow [/math] возвращаем нулевое значение.

Таким образом ответ на полуинтервале [math][1 .. 5)[/math] равен сумме значений в вершинах, отвечающих за полуинтервалы [math][1 .. 2)[/math], [math][2 .. 4)[/math] и [math][4 .. 5)[/math].

Реализация

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

Пусть в узлах дерева хранятся структуры из трех полей:

• [math]left[/math] — левая граница полуинтервала, за который "отвечает" текущая вершина.
• [math]right[/math] — правая граница этого полуинтервала.
• [math] sum[/math] — сумма на полуинтервале.

 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) [math]\subset[/math] [a, b)
           return tree[node].sum;
       int m = (l + r) / 2;
       return get_sum (node * 2 + 1, a, m)
           + get_sum (node * 2 + 2, m + 1, b);
 } 

Ссылки

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

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

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