Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-08-06· OpenAIAi2 WildChat-4.8M (AI2)

Напишите дерево отрезков

  1. User

    Напишите дерево отрезков

  2. 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)
    

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