Всем привет и добро пожаловать в среду для чтенияАлгоритмическая структура данныхТема, сегодня мы поговорим о новой структуре данных под названием дерево сегментов.
Структура данных дерева сегментов линии может немного сбивать с толку многих людей и чувствовать, что они никогда о ней не слышали, но она очень, очень известна, особенно в кругу соревнований, можно сказать, чтоОсновные навыки для соревнований. Поэтому, если вы встретите кого-то, кто прочитал небольшое введение в алгоритмы и притворяется, что находится перед вами, вы можете спросить его: в чем сложность обновления дерева отрезков?
Однако, если вы знаете дерево отрезков, вы должны быть осторожны, лучше не показывать, что вы знаете этот алгоритм случайно во время интервью. В противном случае интервьюер сразу узнает, что вы в кругу, и тогда вы обнаружите, что вопросы интервью после вас гораздо сложнее, чем до. Конечно, также возможно, что интервьюер этого не сделает. Чтобы не смущать вас, вы вынуждены использовать для его завершения решение, не основанное на дереве сегментов. Например, я столкнулся с...
пример
Сказав так много чепухи, что такое дерево отрезков? Дерево отрезков на английском языке - это дерево отрезков, что на самом деле является буквальным переводом. Поскольку эта структура данных не имеет особого отношения к линейным сегментам, лично мне кажется, что она переведена винтервальное деревоМожет чуть ближе.
Давайте сначала поймем, что эта структура данных, вероятно, связана с интервалом. Давайте скажем сначала, давайте посмотрим на пример, чтобы на самом деле понять, зачем нужна структура данных дерева отрезков, и каков его сценарий использования. Таким образом, у нас может быть более интуитивное ощущение.Этот вопрос очень простой и классический.Именно в этом вопросе я столкнулся с внезапной атакой интервьюера, который не разрешил использовать деревья отрезков.
Название этого вопроса таково, учитывая массив длины n. В этом массиве n целых чисел, а затем у нас есть две операции. Операция, называемая обновлением, мыУказывает обновить определенный номер определенной позиции, вторая операция называется запросом по заданному интервалу,Требуется минимальное значение элементов в этом диапазоне.. Каков диапазон n?, количество операций также
, как мы должны этого добиться?
Концепция дерева сегментов линии
Конечно, вы можете уже знать, как использовать дерево сегментов, но вы просто не знаете, что такое дерево сегментов и как его использовать. Если мы сначала отбросим эти сомнения и просто подумаем самым простым образом, мы обнаружим, что каждый наш вопросоперация. В худшем случае мы запрашиваем минимальное значение всего массива, тогда нам нужно обойти весь диапазон по очереди, чтобы найти его. Тогда сложность умножается на количество операций, и сложность всей программы будет достигать
. Очевидно, что это очень большое число, и оно определенно истечет по тайм-ауту в сценарии конкуренции алгоритмов.
То есть просто и грубо сделать это невозможно, если у вас есть достаточный опыт в вопросах, то вы, естественно, подумаете, что нам может понадобиться использовать какие-то структуры данных для оптимизации сложности этого запроса.безусловно неприемлема, даже если она не может быть оптимизирована для
, или хотя бы попробовать
. Дерево отрезков является такой структурой данных.Мы можем непосредственно смотреть на картинку, и мы можем напрямую понять, что делает дерево отрезков и как оно работает.
А на этом рисунке — это массив, в котором мы храним данные, а дерево отрезков над этим массивом — это. Давайте посмотрим на это сверху вниз и объясним это вам. В верхнем ряду есть только одно число — 1, что означаетМинимальное значение всего массива равно 1. То есть верхний слой поддерживает минимальное значение всего интервала. Затем идет второй слой, где мы видим два числа, 3 и 1. Очевидно, что 3 представляет собой минимальное значение левой половины интервала, а 1 представляет собой минимальное значение правой половины интервала.
На третьей строке получаем 4 числа, и аналогично в следующем слое 8 чисел. Очевидно, это бинарное дерево, и в бинарном деревеКаждый узел поддерживает диапазон значений. Его листовые узлы хранят интервал длины 1, то есть один элемент. Мы объединяем интервалы, поддерживаемые двумя родственными узлами, чтобы получить интервал родительского узла. В этой задаче, поскольку мы сохраняем минимальное значение интервала, мы можем получить такую формулу:
node.min = min(node.left.min, node.right.min)
Таким образом, дерево сегментовИспользование иерархии бинарного дереваСтруктура данных, поддерживающая интервал.
Запрос дерева сегментов линии
Мы уже разобрались со структурой дерева отрезков, и осталось только два вопроса, один — как обновить, а другой — как решить. Позвольте мне сначала взглянуть на решение, мы просим минимальное значение интервала. Давайте посмотрим на это на самом деле, что, если мы хотим запросить минимальное значение в интервале [2, 5]?
Сравним приведенный выше массив a, индекс [3, 6] соответствует четырем значениям [7, 9, 6, 4]. мы найдемНе существует интервала, который содержит именно эти четыре значения, то что нам делать? На самом деле это довольно просто собрать вместе. Мы можем обнаружить, что можем преобразовать этот полный интервал в результат объединения двух интервалов. Такие, как на картинке ниже.
Таким образом, мы преобразовали исходное поведение запроса сравнения четырех значений [7, 9, 6, 4] в поведение сравнения, которое требует только сравнения значений 4 и 7. Это может сэкономить нам много времени. Это немного похоже на мемоизированный поиск, который эквивалентен формулированию шаблона и сохранению наибольшего значения в интервале в соответствии с этим шаблоном. Таким образом, мы можем использовать эти значения для быстрого решения при запросе.
Если мы запросим минимальное значение в интервале [2, 7], то вместо этого мы можем использовать значения этих двух интервалов, чтобы найти его.
Обновление дерева сегментов
Далее рассмотрим обновление дерева отрезков, на самом деле принцип обновления и запроса тот же, тот же самыйНачните с корневого узла и спускайтесь вниз слой за слоем, пока обновление не достигнет конечного узла.. Предположим, мы обновим 4 в данных до 0, тогда какой эффект будет достигнут?
Из результата переносим изменённый конечный узел в корень дереваВся эта ссылка была обновлена. Конечно, это обновление не является обязательным, потому что если значение, которое мы обновляем, больше, чем исходное значение 1, оно не будет обновлено.
Код
Мы почти закончили говорить о принципе дерева отрезков, он не выглядит слишком длинным, что нормально. Потому что принцип дерева отрезков на самом деле очень прост, то есть бинарное дерево используется для сохранения интервалов различной длины. Когда мы делаем запрос, мы хотим найти несколько подинтервалов, которые можно объединить в запрашиваемый нами интервал, и использовать значения этих подинтервалов, чтобы найти значение интервала, который мы хотим проверить. Когда мы обновляем, нам не нужно обновлять все дерево, нам нужно только обновить определенный путь от корневого узла к конечному узлу.
Принцип не кажется сложным, и его несложно понять, но реализовать в коде непросто. потому что дерево сегментовВсе операции основаны на рекурсии и возврате, поэтому, если вы хотите плавно и глубоко понять дерево отрезков, вы должны освоить рекурсию и возврат. Иначе дерево отрезков вам будет очень больно писать, а отлаживать после написания будет еще больнее.
Мы будем использовать объектно-ориентированную форму для создания дерева отрезков, конечно, некоторые любят использовать массивы для имитации, это тоже возможно, и суть та же. Сначала создадим класс узла. В этом классе узла хранится 3 значения, одно из нихЗначение поддерживаемого интервала, который поддерживается в этой теме, является интервалом минимума. Один из них — протяженность интервала, левая и правая границы. Другой — левый и правый дочерние узлы.
Поскольку мы не знаем, каковы его левый и правый дочерние элементы и поддерживаемые значения, когда мы создаем узел, мы сначала присваиваем ему значение None.
class Node:
def __init__(self, left_side, right_side):
self.val = None
self.ls, self.rs = left_side, right_side
self.left_child, self.right_child = None, None
После того, как класс Node создан, мы можем использовать его для построения дерева. Давайте сначала рассмотрим метод построения дерева, который часто называют методом построения. Когда мы создаем дерево сегментов, самое главное, чтобы каждый узел в нем хранил минимальное значение соответствующего интервала. Но поскольку дерево отрезков имеет иерархическую структуру, при создании интервала [a, b] мы фактически можем использовать минимальное значение интервала [a, m] и интервала [m+1, b] для получения всего минимальное значение интервала. То есть мы можем использовать левый и правый дочерние узлы текущего узла для завершения, мы говорили об этом ранее.
Посмотрим на код, это удобно сделать с помощью рекурсии.
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.vals = arr[:]
self.root = self.build(0, self.n)
def build(self, l, r):
# 传入的l和r表示区间范围，左闭右开
if r - l < 1:
return None
node = Node(l, r)
# 如果区间长度是1，说明是叶子节点了，直接将val赋值成对应的数值
if r - l == 1:
node.val = self.vals[l]
else:
# 否则递归调用
m = (l + r) >> 1
node.left_child = self.build(l, m)
node.right_child = self.build(m, r)
node.val = min(node.left_child.val, node.right_child.val)
return node
Конечно, этот процесс можно реализовать и в цикле, но проще реализовать его рекурсивно.
Если вы видите метод сборки, то обновление и запрос для вас не проблема, на самом деле принцип тот же, но один рекурсивно обновлять, а другой рекурсивно запрашивать. Давайте сначала посмотрим на обновление:
def update(self, k, v):
self._update(self.root, k, v)
def _update(self, u, k, v):
if u is None:
return
# 如果k在u这个节点维护的区间里
if u.ls <= k < u.rs:
# 更新它的最小值
u.val = min(u.val, v)
m = (u.ls + u.rs) >> 1
# 判断往左还是往右
if k < m:
self._update(u.left_child, k, v)
else:
self._update(u.right_child, k, v)
Наконец, давайте посмотрим на запрос, который также выполняется рекурсивно. Поскольку мы запрашиваем интервал, нам нужно оценить связь между нашим интервалом запроса и интервалом обслуживания узла. Пока это понято, вся логика также очень проста.
def query(self, l, r):
return self._query(self.root, l, r)
def _query(self, u, l, r):
# l和r是查询区间
# 如果查询区间是u节点区间的超集
if l <= u.ls and r >= u.rs:
return u.val
# 如果查询区间只和u节点区间的左半部分有交集
elif r <= u.left_child.rs:
return self._query(u.left_child, l, r)
# 如果查询区间只和u节点右半部分有交集
elif l >= u.right_child.ls:
return self._query(u.right_child, l, r)
# 如果都有交集
return min(self._query(u.left_child, l, r), self._query(u.right_child, l, r))
Наконец
На этом наше основное знакомство с деревьями сегментов закончено. Обратите внимание, что я сказал основное введение, потому чтоДеревья сегментов линии имеют много применений, который является самым простым из них: одноточечный запрос интервала обновления. Кроме тогоЗапрос интервала обновления по одной точке, запрос интервала обновления интервала, строка сканированияИ так далее относительно высококлассного использования. Из-за нехватки места я не могу закончить все сразу, поэтому поделюсь с вами в следующей статье.
Еще один момент заключается в том, что представленные на рынке вопросы по дереву отрезков в основном написаны на C++, поэтому, если вы хотите найти вопрос, который можно попробовать, вам может потребоваться переписать его на C++. Но я считаю, что это не является большой проблемой для вас.
На этом сегодняшняя статья заканчивается. Если вам понравилась эта статья, пожалуйста, помашите мне рукой.Санлианподдержите(Подписывайтесь, делайте репосты, лайкайте).
Оригинальная ссылка, обратите внимание
В этой статье используетсяmdniceнабор текста
- END -