gpt-4o-2024-08-06· OpenAI
WildChat-4.8M (AI2)
Напишите дерево отрезков
- User
Напишите дерево отрезков
- Assistant
Дерево отрезков (или сегментное дерево) — это структура данных, которая позволяет эффективно выполнять определённые операции на подмножествах массива, такие как вычисление суммы, нахождение минимума или максимума, обновление элементов и т.д.
Вот базовая реализация дерева отрезков на языке Python, которая поддерживает операции построения дерева, вычисления суммы на отрезке и обновления элемента:
class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (2 * self.n) # Инициализация листьев for i in range(self.n): self.tree[i + self.n] = data[i] # Построение дерева for i in range(self.n - 1, 0, -1): self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1] def update(self, index, value): # Обновление элемента в массиве pos = index + self.n self.tree[pos] = value while pos > 1: left = pos right = pos if pos % 2 == 0: right = pos + 1 else: left = pos - 1 # Обновление родителя self.tree[pos // 2] = self.tree[left] + self.tree[right] pos //= 2 def query(self, left, right): # Запрос суммы на отрезке [left, right) result = 0 left += self.n right += self.n while left < right: if left % 2 == 1: result += self.tree[left] left += 1 if right % 2 == 1: right -= 1 result += self.tree[right] left //= 2 right //= 2 return result # Пример использования data = [1, 3, 5, 7, 9, 11] seg_tree = SegmentTree(data) # Запрос суммы отрезка [1, 3) print(seg_tree.query(1, 3)) # Вывод: 8 (3 + 5) # Обновление элемента: data[1] = 10 seg_tree.update(1, 10) # Запрос суммы отрезка [1, 3) после обновления print(seg_tree.query(1, 3)) # Вывод: 15 (10 + 5)Этот код создаёт дерево отрезков, которое хранит суммы элементов на различных отрезках входного массива. Он поддерживает обновление отдельных элементов и запросы на сумму на диапазоне в логарифмическое время относительно размера массива.