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

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации запроса сверху вниз, итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее [math]a \circ b[/math].

Построим дерево отрезков, и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:

  1. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева.
  2. Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.
  3. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.
Реализация запроса снизу вверх Ещё один пример
Запрос снизу №1х1.jpg Запрос снизу №2х1.jpg
Запрос снизу №1х2.jpg Запрос снизу №2х2.jpg
Запрос снизу №1х3.jpg Запрос снизу №2х3.jpg
Запрос снизу №1х4.jpg Запрос снизу №2х4.jpg

Псевдокод

Пусть результат считаем на отрезке [math] [left, right] [/math]. При этом значения [math]left[/math] и [math]right[/math], передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные [math]leftRes[/math] и [math]rightRes[/math] будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого.

  int query(left: int, right: int):
     leftRes = neutral
     rightRes = neutral
     while left < right
        if left mod 2 == 0
           leftRes = leftRes [math] \circ [/math] data[left]
        left = left div 2 
        if right mod 2 == 1
           rightRes = data[right] [math] \circ [/math] rightRes
        right = right div 2 - 1
     if left == right  
        leftRes = leftRes [math] \circ [/math] data[left]
     return leftRes [math] \circ [/math] rightRes

См. также

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