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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 5: Строка 5:
 
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).
 
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).
  
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]]  и идет запрос на полуинтервале <tex>[a .. b)</tex>.
+
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]]  и идет запрос на полуинтервале <tex>[a \ldots b)</tex>.
  
 
В качестве параметров рекурсий передаем следующие переменные:
 
В качестве параметров рекурсий передаем следующие переменные:
Строка 14: Строка 14:
 
Запустим рекурсивную процедуру от всего полуинтервала  (то есть от корневой вершины).
 
Запустим рекурсивную процедуру от всего полуинтервала  (то есть от корневой вершины).
  
Для текущего состояния проверяем следующие условия :
+
Для текущего состояния проверяем следующие условия:
  
 
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
 
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;
+
:''Например'': текущий <tex>[1 \ldots 3)</tex>, а искомый <tex>[3 \ldots 5)</tex>;
  
 
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
 
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;
+
:''Например'': текущий <tex>[2 \ldots 3)</tex>, а искомый <tex>[2 \ldots 4)</tex>;
  
 
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
 
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.
Строка 28: Строка 28:
 
==Пример==
 
==Пример==
  
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).
+
Рассмотрим данный алгоритм на примере задачи <tex>\mathrm{RSQ}</tex> (Range Sum Query {{---}} запрос суммы на отрезке).
  
 
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.
 
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.
  
 
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма  
 
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма  
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).
+
{{---}} это отрезок <tex>[1 \ldots 4]</tex> (полуинтервал <tex>[1 \ldots 5)</tex>).
 
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]
 
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]
 
Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):
 
Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):
  
 
* На глубине <tex>0</tex>.  
 
* На глубине <tex>0</tex>.  
** Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> рекурсивно переходим к <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex>
+
** Текущий полуинтервал <tex>[0 \ldots 8)</tex> пересекается с <tex>[1 \ldots 5) \Rightarrow</tex> рекурсивно переходим к <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex>
  
  
 
* На глубине <tex>1</tex>.  
 
* На глубине <tex>1</tex>.  
** <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..
+
** <tex>[0 \ldots 4)</tex> и <tex>[4 \ldots 8)</tex> пересекаются с <tex> [1 \ldots 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 \ldots
  2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex>
+
  2)</tex>, <tex>[2 \ldots 4)</tex>, <tex>[4 \ldots 6)</tex> и <tex>[6 \ldots 8)</tex>
  
  
 
* На глубине <tex>2</tex>.  
 
* На глубине <tex>2</tex>.  
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с  <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>[0 .. 1), [1 .. 2), [4 .. 5), [5 .. 6) </tex>
+
** <tex>[0 \ldots 2)</tex> и <tex>[4 \ldots 6)</tex> пересекаются с  <tex>[1 \ldots 5) \Rightarrow </tex> переходим в листья <tex>[0 \ldots 1), [1 \ldots 2), [4 \ldots 5), [5 \ldots 6) </tex>
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
+
** <tex>[2 \ldots 4) </tex> полностью лежит внутри <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем сумму на этом отрезке
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение
+
** <tex>[6 \ldots 8)</tex> не пересекается с <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем нулевое значение
  
  
 
* На глубине <tex>3</tex>.  
 
* На глубине <tex>3</tex>.  
** Листья <tex>[1 .. 2), [4 .. 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
+
** Листья <tex>[1 \ldots 2), [4 \ldots 5)</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них
** Листья <tex>[0 .. 1), [5 .. 6)</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нейтральное значение
+
** Листья <tex>[0 \ldots 1), [5 \ldots 6)</tex> лежат вне <tex>[1 \ldots 5) \Rightarrow </tex> возвращаем нейтральное значение
  
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.
+
Таким образом ответ на полуинтервале <tex>[1 \ldots 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 \ldots 2)</tex>, <tex>[2 \ldots 4)</tex> и <tex>[4 \ldots 5)</tex>.
  
 
==Реализация==
 
==Реализация==
Строка 62: Строка 62:
  
 
Пусть в узлах дерева хранятся структуры из трех полей:
 
Пусть в узлах дерева хранятся структуры из трех полей:
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
+
* <tex>\mathtt{left}</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
+
* <tex>\mathtt{right}</tex> {{---}} правая граница этого полуинтервала.
* <tex> res</tex> {{---}} результат операции на полуинтервале.
+
* <tex> \mathtt{res}</tex> {{---}} результат операции на полуинтервале.
  
 
   '''int''' query('''int''' node, '''int''' a, '''int''' b)     
 
   '''int''' query('''int''' node, '''int''' a, '''int''' b)     

Текущая версия на 19:22, 4 сентября 2022

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

Алгоритм

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

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

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

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

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

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

  • Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.
Например: текущий [math][1 \ldots 3)[/math], а искомый [math][3 \ldots 5)[/math];
  • Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.
Например: текущий [math][2 \ldots 3)[/math], а искомый [math][2 \ldots 4)[/math];
  • Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.

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

Пример

Рассмотрим данный алгоритм на примере задачи [math]\mathrm{RSQ}[/math] (Range Sum Query — запрос суммы на отрезке).

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

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

Пример рабoты алгоритма

Рассмотрим данный алгоритм на определенных глубинах рекурсии, то есть на разных уровнях дерева (на рисунке глубина обозначена слева от уровня):

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


  • На глубине [math]1[/math].
    • [math][0 \ldots 4)[/math] и [math][4 \ldots 8)[/math] пересекаются с [math] [1 \ldots 5) \Rightarrow [/math] переходим по рекурсивным вызовам на полуинтервалах [math][0 \ldots 2)[/math], [math][2 \ldots 4)[/math], [math][4 \ldots 6)[/math] и [math][6 \ldots 8)[/math]


  • На глубине [math]2[/math].
    • [math][0 \ldots 2)[/math] и [math][4 \ldots 6)[/math] пересекаются с [math][1 \ldots 5) \Rightarrow [/math] переходим в листья [math][0 \ldots 1), [1 \ldots 2), [4 \ldots 5), [5 \ldots 6) [/math]
    • [math][2 \ldots 4) [/math] полностью лежит внутри [math][1 \ldots 5) \Rightarrow [/math] возвращаем сумму на этом отрезке
    • [math][6 \ldots 8)[/math] не пересекается с [math][1 \ldots 5) \Rightarrow [/math] возвращаем нулевое значение


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

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

Реализация

Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.

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

  • [math]\mathtt{left}[/math] — левая граница полуинтервала, за который "отвечает" текущая вершина.
  • [math]\mathtt{right}[/math] — правая граница этого полуинтервала.
  • [math] \mathtt{res}[/math] — результат операции на полуинтервале.
 int query(int node, int a, int b)     
     l = tree[node].left
     r = tree[node].right 
     if [l, r) [math]\cap [/math] [a, b) == [math]\varnothing[/math]
         return [math]\varepsilon[/math]                    // [math]\varepsilon[/math] — нейтральный для данной операции элемент
     if [l, r) [math]\subset[/math] [a, b)
         return tree[node].res
     return query(node * 2 + 1, a, b) [math] \circ [/math] query(node * 2 + 2, a, b)

См. также

Источники информации