Первоначально опубликовано на Seedbx.com 21 февраля 2021 г.

Часто нам приходится работать с сегментами или интервалами списка элементов. Именно здесь среди многих других появляется дерево сегментов.

В этом посте мы узнаем об этой красивой структуре данных, а именно о дереве сегментов.

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

Дерево сегментов

В информатике дерево сегментов, также известное как дерево статистики, представляет собой древовидную структуру данных, используемую для хранения информации об интервалах или сегментах (отсюда и название). Дерево отрезков было изобретено Джоном Бентли в 1977 году в его статье Решения задач прямоугольника Клее.

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

Структура

Дерево сегментов содержит следующие свойства:

  • Дерево сегментов является бинарным деревом.
  • Листья дерева отрезков соответствуют элементам массива элементов, из которых строится дерево.
  • Внутренние узлы дерева представляют собой интервалы элементов массива элементов, образованного объединением интервалов, представленных его левым и правым дочерними элементами.
  • Для массива размером n размер дерева сегментов равен

Внутри дерево сегментов хранится в виде массива, где для узла с индексом i его левый дочерний элемент имеет индекс 2*i+1, а его правый дочерний элемент находится по индексу 2*i+2.

Строить

buildSegmentTree – это рекурсивная процедура, которая строит дерево сегментов из базового массива. Процедура использует подход «разделяй и властвуй» для построения дерева сегментов.

  1. массив : базовый массив, из которого строится дерево сегментов.
  2. left : индекс левой стороны сегмента.
  3. right : индекс правой стороны сегмента.
  4. index : индекс элемента в дереве сегментов, в котором хранится информация об элементах сегмента массив[слева]…массив[справа].

Он принимает четыре параметра:

  1. Разделить . На этом этапе процедура разбивает сегмент на два подсегмента.
  2. Покорение: на этом этапе процедура рекурсивно решает подсегменты с базовым случаем, возникающим, когда сегмент состоит только из одного элемента, в соответствии с чем segmentTree[index]=array[left]
  3. Объединить . На этом этапе процедура объединяет решения для двух подсегментов (левого и правого дочерних) с помощью функции func, чтобы получить решение для сегмента.

Псевдокод:

Как и любая другая процедура «разделяй и властвуй», эта процедура состоит из трех шагов:

Временная сложность: O(N)

buildSegmentTree(array,left,right,index)
  if left<right return if left==right
    segmentTree[index]=array[left]
    return mid=(left+right)
  buildSegmentTree(array,left,mid,2*index+1)
  buildSegmentTree(array,mid+1,right,2*index+2)
  segmentTree[index]=func(segmentTree[2*index+1],segmentTree[2*index+2])

Запрос

querySegmentTree возвращает значение func( начало…конец) для заданного сегмента начало…конец.

  1. left : левый индекс сегмента в segmentTree[index].
  2. right : Правый индекс сегмента в segmentTree[index].
  3. index : индекс текущего элемента дерева сегментов.
  4. start : левый индекс нужного сегмента.
  5. конец : правый индекс нужного сегмента.
  6. val : значение func(start…end), которое должно быть возвращено в конце.

Процедура querySegmentTree принимает шесть аргументов:

  1. Сегмент start…end полностью или частично находится внутри сегмента: в этой ситуации мы просто рекурсивно вызываем querySegmentTree как для левого, так и для правого дочерних элементов.
  2. Сегмент начало…конец находится полностью за пределами сегмента: в этой ситуации у нас нет шансов достичь какого-либо элемента в segmentTree, который является частью сегмента начало…конец, поэтому мы просто возвращаемся
  3. Сегмент полностью находится внутри сегмента начало…конец: в этой ситуации мы достигли части сегмента начало…конец и, следовательно, мы просто добавляем значение в segmentTree [индекс] к знач.

Псевдокод:

Для каждого сегмента слева… справа могут возникнуть три ситуации:

Временная сложность: O(log(N))

querySegmentTree(left,right,index,start,end,val)
  if left>start&&right<end
    return
  if left<=start&&right>=end
    val=func(val,segmentTree[index])
    return
  mid=(left+right)/2
  querySegmentTree(left,mid,2*index+1,start,end,val)
  querySegmentTree(mid+1,right,2*index+2,start,end,val)

Обновлять

updateSegmentTree – это простая процедура, которая обновляет заданную позицию в базовом массиве и перестраивает все дерево сегментов с обновленным массивом.

  1. массив: базовый массив, из которого было построено дерево сегментов.
  2. left : левый индекс сегмента в segmentTree[index].
  3. right : Правый индекс сегмента в segmentTree[index].
  4. index : индекс текущего элемента дерева сегментов.
  5. pos : индекс позиции, которую необходимо изменить.
  6. val : новое значение, которое будет присвоено массиву [index]

Псевдокод:

Процедура updateSegmentTree принимает шесть аргументов:

Временная сложность: O(log(N))

updateSegmentTree(array,left,right,index,pos,val)
  if left==right
    array[pos]=val
    segmentTree[index]=val
    return
  mid=(left+right)/2
  if pos<=mid
    updateSegmentTree(array,left,mid,2*index+1,pos,val)
  else
    updateSegmentTree(array,mid+1,right,2*index+2,pos,val)
  segmentTree[index]=func(segmentTree[2*index+1],segmentTree[2*index+2])

Деревья сегментов являются очень хорошей структурой данных в ситуациях, когда запросы сегментов или диапазонов являются очень распространенным делом. Однако структура данных очень похожа на дерево сегментов, известное как Дерево Фенвика (FT) или Двоичное индексированное дерево (BIT), но мы рассмотрим эту структуру данных позже. момент времени.

Спасибо, что прочитали статью!

Если у вас есть вопросы, оставьте комментарий ниже. Не забудьте поставить аплодисменты, если вам понравилась статья.

Первоначально опубликовано на сайте Seedbx.com 21 февраля 2021 г.