Требует ли рекурсивное дерево сегментов больше места, чем итеративное?
Я изучаю структуру данных дерева сегментов.
Я видел несколько итеративных деревьев сегментов, которые используют только 2n пространства. Поэтому я попытался использовать тот же метод сборки в дереве сегментов с рекурсивным обновлением и sumRange. Это не разрешено? Почему итеративное дерево сегментов может храниться в 2n, а рекурсивное — в 4n? Или у меня просто дефект реализации в моем нерабочем дереве?
Для моего дерева 2n я использую дерево с индексом 1, поэтому в tree[0] ничего не хранится. Это означает, что корень находится в tree[1]. Я делаю рекурсивные вызовы, используя начальный диапазон от 1 до n - 1, в чем я не уверен. Я получаю разные неправильные ответы, когда перехожу к self.n или начинаю с 0. Я также получаю разные неправильные ответы, если передаю index+1, left+1 или right+1.
Вот моя реализация:
class NumArray:
# Classic Segment Tree
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0] * self.n * 2
self.build(nums)
def build(self, nums):
# leaves
for i in range(self.n):
self.tree[i + self.n] = nums[i]
# internal
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
def merge(self, left, right):
return left + right
def _update(self, tree_idx, seg_left, seg_right, i, val):
# leaf
if seg_left == seg_right:
self.tree[tree_idx] = val
return
mid = (seg_left + seg_right) // 2
if i > mid:
self._update(tree_idx * 2 + 1, mid + 1, seg_right, i, val)
else:
self._update(tree_idx * 2, seg_left, mid, i, val)
self.tree[tree_idx] = self.merge(self.tree[tree_idx * 2], self.tree[tree_idx * 2 + 1])
def update(self, index: int, val: int) -> None:
self._update(1, 1, self.n - 1, index, val)
def _sumRange(self, tree_idx, seg_left, seg_right, query_left, query_right):
# segment out of query bounds
if seg_left > query_right or seg_right < query_left:
return 0
# segment fully in bounds
if seg_left >= query_left and seg_right <= query_right:
return self.tree[tree_idx]
# segment partially in bounds
mid = (seg_left + seg_right) // 2
# this is not necessary for correctness, but helps with efficiency (we only go down 1 path if 2 is unnecessary)
if query_left > mid:
return self._sumRange(tree_idx * 2 + 1, mid + 1, seg_right, query_left, query_right)
elif query_right <= mid:
return self._sumRange(tree_idx * 2, seg_left, mid, query_left, query_right)
left_sum = self._sumRange(tree_idx * 2, seg_left, mid, query_left, query_right)
right_sum = self._sumRange(tree_idx * 2 + 1, mid + 1, seg_right, query_left, query_right)
return self.merge(left_sum, right_sum)
def sumRange(self, left: int, right: int) -> int:
return self._sumRange(1, 1, self.n - 1, left, right)
У меня есть работающая полностью рекурсивная версия с нулевым индексом, но она использует вдвое больше места.
class NumArray:
# Classic Segment Tree
# 0-indexed recursive
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0] * self.n * 4
self.build(nums, 0, 0, self.n - 1)
def build(self, nums, tree_idx, left, right):
# leaf
if left == right:
self.tree[tree_idx] = nums[left]
return
mid = (left + right) // 2
self.build(nums, tree_idx * 2 + 1, left, mid)
self.build(nums, tree_idx * 2 + 2, mid + 1, right)
self.tree[tree_idx] = self.tree[tree_idx * 2 + 1] + self.tree[tree_idx * 2 + 2]
def merge(self, left, right):
return left + right
def _update(self, tree_idx, seg_left, seg_right, i, val):
# leaf
if seg_left == seg_right:
self.tree[tree_idx] = val
return
mid = (seg_left + seg_right) // 2
if i > mid:
self._update(tree_idx * 2 + 2, mid + 1, seg_right, i, val)
else:
self._update(tree_idx * 2 + 1, seg_left, mid, i, val)
self.tree[tree_idx] = self.merge(self.tree[tree_idx * 2 + 1], self.tree[tree_idx * 2 + 2])
def update(self, index: int, val: int) -> None:
self._update(0, 0, self.n - 1, index, val)
def _sumRange(self, tree_idx, seg_left, seg_right, query_left, query_right):
# segment out of query bounds
if seg_left > query_right or seg_right < query_left:
return 0
# segment fully in bounds
if seg_left >= query_left and seg_right <= query_right:
return self.tree[tree_idx]
# segment partially in bounds
mid = (seg_left + seg_right) // 2
# this is not necessary for correctness, but helps with efficiency (we only go down 1 path if 2 is unnecessary)
if query_left > mid:
return self._sumRange(tree_idx * 2 + 2, mid + 1, seg_right, query_left, query_right)
elif query_right <= mid:
return self._sumRange(tree_idx * 2 + 1, seg_left, mid, query_left, query_right)
left_sum = self._sumRange(tree_idx * 2 + 1, seg_left, mid, query_left, query_right)
right_sum = self._sumRange(tree_idx * 2 + 2, mid + 1, seg_right, query_left, query_right)
return self.merge(left_sum, right_sum)
def sumRange(self, left: int, right: int) -> int:
return self._sumRange(0, 0, self.n - 1, left, right)
Этот сайт проверяет правильность реализации дерева сегментов.
Также я знаю, что рекурсия использует больше места в стеке вызовов. Мой вопрос не об этом
@ user24714692 Это полностью итеративно. Можем ли мы сохранить мое рекурсивное обновление и sumRange, а также итеративную сборку только для 2n пространства?
Я бы предложил итеративный подход. Но, если вы настаиваете, вы можете попробовать получить гибрид ST. Как вы знаете, рекурсия требует дополнительного стека вызовов.
Ответы 1
Фактически, стандартное рекурсивное дерево сегментов легко изменить, чтобы использовать 2N узлов вместо 4N. Часто можно увидеть выделенный массив из 4N узлов, потому что он прост и не требует особых размышлений, но может остаться много неиспользуемого пространства.
Обратите внимание, что дерево сегментов представляет собой полное бинарное дерево с N листьями, поэтому внутренних узлов должно быть N - 1 (это легко увидеть по индукции). Таким образом, нам действительно требуется только 2N–1 узлов, и мы можем оптимизировать использование памяти, изменив порядок хранения узлов.
После любого узла мы можем хранить все его левое поддерево, а затем все правое поддерево в последовательных позициях в массиве, представляющем дерево сегментов. Для узла с индексом i его левый дочерний элемент следует непосредственно за ним с индексом i + 1. Его правый дочерний элемент следует непосредственно за последним элементом левого поддерева. Левое поддерево также является полным двоичным деревом и представляет диапазон [left, mid], поэтому имеется mid - left + 1 листовых узлов. Таким образом, всего в левом поддереве 2 * (mid - left + 1) - 1 узлов. Мы добавляем 1, чтобы перейти к правильному дочернему элементу, поэтому правильный дочерний элемент находится под индексом i + 2 * (mid - left + 1). Учитывая это, остальные операции с деревом сегментов остаются прежними.
class NumArray:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0] * 2 * self.n
self.build(nums, 0, 0, self.n - 1)
def merge(self, left_val, right_val):
return left_val + right_val
def build(self, nums, tree_idx, left, right):
if left == right:
self.tree[tree_idx] = nums[left]
else:
mid = left + right >> 1
self.tree[tree_idx] = self.merge(self.build(nums, tree_idx + 1, left, mid),
self.build(nums, tree_idx + 2 * (mid - left + 1), mid + 1, right))
return self.tree[tree_idx]
def _update(self, tree_idx, left, right, i, val):
if left == right:
self.tree[tree_idx] = val
else:
mid = left + right >> 1
if i > mid:
self._update(tree_idx + 2 * (mid - left + 1), mid + 1, right, i, val)
else:
self._update(tree_idx + 1, left, mid, i, val)
self.tree[tree_idx] = self.merge(self.tree[tree_idx + 1], self.tree[tree_idx + 2 * (mid - left + 1)])
def update(self, index: int, val: int) -> None:
return self._update(0, 0, self.n - 1, index, val)
def _sumRange(self, tree_idx, seg_left, seg_right, query_left, query_right):
if query_left > query_right:
return 0
if seg_left == query_left and seg_right == query_right:
return self.tree[tree_idx]
mid = seg_left + seg_right >> 1
return self.merge(self._sumRange(tree_idx + 1, seg_left, mid, query_left, min(mid, query_right)),
self._sumRange(tree_idx + 2 * (mid - seg_left + 1), mid + 1, seg_right, max(mid + 1, query_left), query_right))
def sumRange(self, left: int, right: int) -> int:
return self._sumRange(0, 0, self.n - 1, left, right)
Хороший! Итак, рекуррентное отношение между родителями и детьми меняется, когда вы переходите к 2N - интересно. Почему при итерации стандартное рекуррентное соотношение сохраняется с размером 2N?
@Alec Стандартное итеративное дерево сегментов, построенное для размера, не являющегося степенью 2, на самом деле не хранит элементы в том же порядке, что и стандартное рекурсивное, поэтому я бы не сказал, что стандартная рекурсия сохраняется. Это только так выглядит, но базовая структура может отличаться от тех значений, которые вы ожидаете в каждом узле (попробуйте распечатать значения).