Segment Tree

Дерево отрезков для диапазонных запросов (сумма, минимум, максимум) и обновлений. Построение O(n), запрос O(log n).

#1. Суть паттерна

Segment Tree (Дерево отрезков) — это древовидная структура данных для эффективных диапазонных запросов и обновлений. Каждый узел дерева представляет отрезок массива и хранит агрегированное значение (сумму, минимум, максимум и т.д.).

#1.1 Термины

Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.

Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.

Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.

Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.

#Когда применять

✅ Диапазонные запросы — сумма, минимум, максимум на отрезке [L, R]
✅ Точечные обновления — изменение элемента массива с пересчётом запросов
✅ Множественные запросы — когда нужно выполнить много запросов к одному массиву
✅ Динамический массив — когда массив меняется между запросами
✅ Сложные агрегации — не только сумма, но и другие ассоциативные операции

#Предусловия

Ассоциативность операции — (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
Статический размер — размер массива известен заранее
Индексы 0-based — стандартная нумерация

#Структура

Массив: [1, 3, 5, 7, 9, 11]

Дерево отрезков (сумма):
                    [0-5: 36]
                   /         \
           [0-2: 9]           [3-5: 27]
          /       \           /       \
     [0-1: 4]    [2-2: 5]  [3-4: 16]  [5-5: 11]
     /    \                  /    \
 [0-0:1] [1-1:3]      [3-3:7] [4-4:9]

#Сравнение с альтернативами

Задача	Segment Tree	Fenwick Tree	Prefix Sum	Naive
Сумма на отрезке	✅ O(log n)	✅ O(log n)	✅ O(1)	❌ O(n)
Минимум на отрезке	✅ O(log n)	❌ Нет	❌ Нет	❌ O(n)
Точечное обновление	✅ O(log n)	✅ O(log n)	❌ O(n)	✅ O(1)
Универсальность	✅ Высокая	⚠️ Только сумма	❌ Низкая	✅ Любая
Простота реализации	⚠️ Средняя	✅ Простая	✅ Простая	✅ Простая

Вывод: Segment Tree универсальнее Fenwick, но сложнее в реализации. Используйте Fenwick для простых сумм, Segment Tree — для минимумов/максимумов и сложных операций.

#2. Шаблон

#Sum Segment Tree

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 0, 0, self.n - 1)

    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            self.build(data, 2*node + 1, start, mid)
            self.build(data, 2*node + 2, mid + 1, end)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def update(self, idx, val):
        self._update(0, 0, self.n - 1, idx, val)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self._update(2*node + 1, start, mid, idx, val)
            else:
                self._update(2*node + 2, mid + 1, end, idx, val)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def query(self, left, right):
        return self._query(0, 0, self.n - 1, left, right)

    def _query(self, node, start, end, left, right):
        if right < start or left > end:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2*node + 1, start, mid, left, right) +
                self._query(2*node + 2, mid + 1, end, left, right))

#3. Разбор задач

#Задача 1: Range Sum Query - Mutable (LeetCode 307) 🟦 Medium

Ссылка: https://leetcode.com/problems/range-sum-query-mutable/

Условие: Реализуйте класс NumArray для работы с целочисленным массивом nums:

update(index, val) — обновляет значение nums[index] на val
sumRange(left, right) — возвращает сумму элементов от left до right включительно

Примеры:

Ввод: ["NumArray", "sumRange", "update", "sumRange"]
      [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Вывод: [null, 9, null, 8]
Объяснение: 
  NumArray numArray = new NumArray([1, 3, 5]);
  numArray.sumRange(0, 2); // 1 + 3 + 5 = 9
  numArray.update(1, 2);   // nums = [1, 2, 5]
  numArray.sumRange(0, 2); // 1 + 2 + 5 = 8

Ограничения:

1 <= nums.length <= 3 × 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100

💡 Подсказка: Используйте Segment Tree для эффективных обновлений и диапазонных запросов суммы.

#Визуализация

Массив: [1, 3, 5, 7, 9, 11]

Построение дерева (сумма):
                    [0-5: 36]
                   /         \
           [0-2: 9]           [3-5: 27]
          /       \           /       \
     [0-1: 4]    [2-2: 5]  [3-4: 16]  [5-5: 11]
     /    \                  /    \
 [0-0:1] [1-1:3]      [3-3:7] [4-4:9]

Каждый узел хранит сумму диапазона:
- Листья: отдельные элементы
- Внутренние узлы: сумма детей

Запрос sum(1, 4) для [1, 3, 5, 7, 9, 11]:

                    [0-5: 36]
                   /         \
           [0-2: 9]           [3-5: 27]
          /       \           /       \
     [0-1: 4]    [2-2: 5]  [3-4: 16]  [5-5: 11]
     /    \                  /    \
 [0-0:1] [1-1:3]      [3-3:7] [4-4:9]
    ↑                           ↑
    └─────── запрос [1,4] ──────┘

Разбиваем запрос:
- [1,1]: берём [1-1:3]
- [2,2]: берём [2-2:5]
- [3,4]: берём [3-4:16]

Сумма: 3 + 5 + 16 = 24

Решение:

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 0, 0, self.n - 1)

    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            self.build(data, 2*node + 1, start, mid)
            self.build(data, 2*node + 2, mid + 1, end)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def update(self, idx, val):
        self._update(0, 0, self.n - 1, idx, val)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self._update(2*node + 1, start, mid, idx, val)
            else:
                self._update(2*node + 2, mid + 1, end, idx, val)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def query(self, left, right):
        return self._query(0, 0, self.n - 1, left, right)

    def _query(self, node, start, end, left, right):
        if right < start or left > end:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2*node + 1, start, mid, left, right) +
                self._query(2*node + 2, mid + 1, end, left, right))

class NumArray:
    def __init__(self, nums):
        self.st = SegmentTree(nums)

    def update(self, index, val):
        self.st.update(index, val)

    def sumRange(self, left, right):
        return self.st.query(left, right)

Объяснение:

Segment Tree строится за O(n)
update: O(log n) — обновляем путь от листа к корню
query: O(log n) — рекурсивный запрос диапазона

Сложность:

Время: O(n) построение, O(log n) update/query
Память: O(n)

#Задача 2: Count of Smaller Numbers After Self (LeetCode 315) 🔴 Hard

Ссылка: https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Условие: Дан целочисленный массив nums. Верните массив counts, где counts[i] — количество элементов меньше nums[i], находящихся справа от nums[i].

Примеры:

Ввод: nums = [5,2,6,1]
Вывод: [2,1,1,0]
Объяснение:
  5: справа есть 2 и 1 (меньше) → 2
  2: справа есть 1 (меньше) → 1
  6: справа есть 1 (меньше) → 1
  1: справа нет элементов → 0

Ввод: nums = [-1,-1]
Вывод: [0,0]

Ограничения:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

💡 Подсказка: Используйте Fenwick Tree (Binary Indexed Tree) со сжатием координат. Проходите справа налево.

Решение:

def countSmaller(nums):
    if not nums:
        return []

    # Сжимаем значения до диапазона [0, n-1]
    sorted_nums = sorted(set(nums))
    rank_map = {v: i for i, v in enumerate(sorted_nums)}
    n = len(sorted_nums)

    # Fenwick Tree
    tree = [0] * (n + 1)

    def update(i, delta=1):
        i += 1  # 1-based indexing
        while i <= n:
            tree[i] += delta
            i += i & (-i)

    def query(i):
        i += 1
        result = 0
        while i > 0:
            result += tree[i]
            i -= i & (-i)
        return result

    result = []
    # Проходим справа налево
    for num in reversed(nums):
        rank = rank_map[num]
        # Количество элементов меньше текущего
        result.append(query(rank - 1))
        # Добавляем текущий элемент
        update(rank)

    return result[::-1]

Объяснение:

Сжатие координат: отображаем значения в [0, n-1]
Проходим справа налево
query(rank - 1) — количество элементов меньше текущего
update(rank) — добавляем текущий элемент в дерево

Сложность:

Время: O(n log n)
Память: O(n)

#Задача 3: The Skyline Problem (LeetCode 218) 🔴 Hard

Ссылка: https://leetcode.com/problems/the-skyline-problem/

Условие: Городская skyline — это контур, образованный зданиями при просмотре издалека. Даны прямоугольные здания в формате [left, right, height].

Верните ключевые точки skyline в формате [[x1,y1],[x2,y2],...].

Примеры:

Ввод: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Вывод: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Ввод: buildings = [[0,2,3],[2,5,3]]
Вывод: [[0,3],[5,0]]

Ограничения:

1 <= buildings.length <= 10⁴
0 <= left < right <= 2³¹ - 1
1 <= height <= 2³¹ - 1

💡 Подсказка: Используйте events (начало/конец здания) и max-heap для отслеживания текущей высоты.

Решение:

import heapq

def getSkyline(buildings):
    # События: (x, -height, right) для начала, (right, 0, 0) для конца
    events = []
    for left, right, height in buildings:
        events.append((left, -height, right))  # Отрицательная высота для сортировки
        events.append((right, 0, 0))

    events.sort()
    result = []
    heap = [(0, float('inf'))]  # (height, end) — max-heap по высоте

    for start, height, end in events:
        # Удаляем здания, закончившиеся до start
        while heap[0][1] <= start:
            heapq.heappop(heap)

        if height < 0:  # Новое здание
            heapq.heappush(heap, (height, end))

        # Если высота изменилась — добавляем точку
        if not result or result[-1][1] != -heap[0][0]:
            result.append([start, -heap[0][0]])

    return result

Объяснение:

events: начало здания (с отрицательной высотой для сортировки) и конец
heap хранит (height, end) — активные здания
При начале: добавляем здание в heap
При изменении максимальной высоты: добавляем ключевую точку

Сложность:

Время: O(n log n)
Память: O(n)

#Задача 4: Reverse Pairs (LeetCode 493) 🔴 Hard

Ссылка: https://leetcode.com/problems/reverse-pairs/

Условие: Дан целочисленный массив nums. Верните количество reverse pairs, где:

0 <= i < j < nums.length
nums[i] > 2 * nums[j]

Примеры:

Ввод: nums = [1,3,2,3,1]
Вывод: 2
Объяснение: (3,1) и (3,1)

Ввод: nums = [2,4,3,5,1]
Вывод: 3
Объяснение: (4,1), (3,1), (5,1)

Ограничения:

1 <= nums.length <= 5 × 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

💡 Подсказка: Используйте модифицированную сортировку слиянием. Во время слияния считайте пары.

Решение:

def reversePairs(nums):
    def merge_sort(left, right):
        if left >= right:
            return 0

        mid = (left + right) // 2
        count = merge_sort(left, mid) + merge_sort(mid + 1, right)

        # Считаем reverse pairs
        j = mid + 1
        for i in range(left, mid + 1):
            while j <= right and nums[i] > 2 * nums[j]:
                j += 1
            count += j - (mid + 1)

        # Сортируем слиянием
        nums[left:right + 1] = sorted(nums[left:right + 1])

        return count

    return merge_sort(0, len(nums) - 1)

Объяснение:

Разделяем массив пополам (merge sort)
Перед слиянием считаем reverse pairs: для каждого элемента левой половины находим, сколько элементов правой удовлетворяют условию
Сортируем для корректной работы на верхних уровнях

Сложность:

Время: O(n log n)
Память: O(n)

#Задача 5: Range Module (LeetCode 715) 🔴 Hard

Ссылка: https://leetcode.com/problems/range-module/

Условие: Реализуйте класс RangeModule для отслеживания числовых диапазонов:

addRange(left, right) — добавляет диапазон [left, right)
queryRange(left, right) — проверяет, полностью ли покрыт диапазон
removeRange(left, right) — удаляет диапазон

Примеры:

Ввод: ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
      [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Вывод: [null, null, null, true, false, true]

Ограничения:

1 <= left < right <= 10⁹
До 10⁴ вызовов каждого метода

💡 Подсказка: Используйте отсортированный список непересекающихся интервалов. При добавлении объединяйте пересекающиеся.

Решение:

class RangeModule:
    def __init__(self):
        self.ranges = []  # Список непересекающихся интервалов

    def addRange(self, left, right):
        new_ranges = []
        for start, end in self.ranges:
            if right < start:
                new_ranges.append((start, end))
            elif left > end:
                new_ranges.append((start, end))
            else:
                # Пересекается — объединяем
                left = min(left, start)
                right = max(right, end)
        new_ranges.append((left, right))
        self.ranges = sorted(new_ranges)

    def queryRange(self, left, right):
        for start, end in self.ranges:
            if start <= left and right <= end:
                return True
            if start > left:
                return False
        return False

    def removeRange(self, left, right):
        new_ranges = []
        for start, end in self.ranges:
            if right < start:
                new_ranges.append((start, end))
            elif left > end:
                new_ranges.append((start, end))
            else:
                # Пересекается — разбиваем
                if start < left:
                    new_ranges.append((start, left))
                if right < end:
                    new_ranges.append((right, end))
        self.ranges = sorted(new_ranges)

Объяснение:

addRange: объединяем все пересекающиеся интервалы в один
queryRange: проверяем, существует ли интервал, полностью покрывающий [left, right)
removeRange: разбиваем интервалы, пересекающиеся с удаляемым

Сложность:

Время: O(n) для каждого метода (n — количество интервалов)
Память: O(n)

#4. Fenwick Tree (Binary Indexed Tree)

class FenwickTree:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1  # 1-based indexing
        while i <= len(self.tree) - 1:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        i += 1
        result = 0
        while i > 0:
            result += self.tree[i]
            i -= i & (-i)
        return result

    def range_query(self, left, right):
        return self.query(right) - self.query(left - 1)

#5. Шпаргалка

Задача	Структура	Ключевая идея
Range Sum Query	Segment Tree	update/query за O(log n)
Count Smaller	Fenwick + сжатие	Справа налево, query(rank-1)
Skyline	Heap + events	Max-heap активных зданий
Reverse Pairs	Merge Sort	Подсчёт во время слияния
Range Module	Список интервалов	Объединение/разбиение

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильный размер массива tree

Проблема: Недостаточно памяти.

# ❌ Неправильно
self.tree = [0] * (2 * n)  # Мало!

# ✅ Правильно
self.tree = [0] * (4 * n)  # Достаточно для полного дерева

Почему это неправильно: Для n элементов нужно до 4n узлов.

#❌ Ошибка 2: Неправильный mid

Проблема: Выход за границы.

# ❌ Неправильно
mid = (start + end) // 2  # Может переполниться!

# ✅ Правильно
mid = start + (end - start) // 2

Почему это неправильно: Сумма может превысить max int.

#❌ Ошибка 3: Неправильные границы детей

Проблема: Бесконечная рекурсия.

# ❌ Неправильно
self.build(data, 2*node, start, mid)  # Должно быть 2*node+1!

# ✅ Правильно
self.build(data, 2*node + 1, start, mid)  # Левый ребёнок
self.build(data, 2*node + 2, mid + 1, end)  # Правый ребёнок

Почему это неправильно: Индексы детей: 2node+1 и 2node+2.

#❌ Ошибка 4: Пропуск проверки пересечения

Проблема: Неверные результаты.

# ❌ Неправильно
def _query(self, node, start, end, left, right):
    # Нет проверки на непересечение!
    if left <= start and end <= right:
        return self.tree[node]

# ✅ Правильно
def _query(self, node, start, end, left, right):
    if right < start or left > end:  # Не пересекается!
        return 0
    if left <= start and end <= right:
        return self.tree[node]

Почему это неправильно: Нужно проверять непересекающиеся диапазоны.

#❌ Ошибка 5: Выбор Fenwick вместо Segment Tree

Проблема: Fenwick не поддерживает все операции.

# ❌ Неправильно — Fenwick для минимума
# Fenwick поддерживает только суммы!

# ✅ Правильно — Segment Tree для минимума/максимума

Почему это неправильно: Fenwick работает только с ассоциативными операциями типа суммы.

#7. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Реализуйте структуру данных для суммы диапазона с обновлением элемента.

Пример:

Ввод: ["NumArray", "sumRange", "update", "sumRange"]
      [[[1,3,5]], [0,2], [1,2], [0,2]]
Вывод: [null, 9, null, 8]
Объяснение: sum(0,2)=9, update(1,2), sum(0,2)=8

💡 Подсказка 1

Используйте Segment Tree для O(log n) операций

💡 Подсказка 2

Дерево хранит суммы диапазонов

💡 Подсказка 3

4*n размера достаточно для дерева

✅ Решение

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 0, 0, self.n - 1)
    
    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = start + (end - start) // 2
            self.build(data, 2*node+1, start, mid)
            self.build(data, 2*node+2, mid+1, end)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def update(self, idx, val):
        self._update(0, 0, self.n-1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = start + (end - start) // 2
            if start <= idx <= mid:
                self._update(2*node+1, start, mid, idx, val)
            else:
                self._update(2*node+2, mid+1, end, idx, val)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def query(self, left, right):
        return self._query(0, 0, self.n-1, left, right)
    
    def _query(self, node, start, end, left, right):
        if right < start or left > end:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = start + (end - start) // 2
        return (self._query(2*node+1, start, mid, left, right) +
                self._query(2*node+2, mid+1, end, left, right))

class NumArray:
    def __init__(self, nums):
        self.st = SegmentTree(nums)
    
    def update(self, index, val):
        self.st.update(index, val)
    
    def sumRange(self, left, right):
        return self.st.query(left, right)

Объяснение:

build: O(n) построение дерева
update: O(log n) обновление элемента
query: O(log n) сумма диапазона

Сложность:

Время: O(n) построение, O(log n) операции
Память: O(n) дерево

#8. Заключение

Segment Tree для сложных диапазонных запросов:

Построение: O(n)
Запрос/обновление: O(log n)
Память: O(n)

Fenwick Tree проще для сумм:

Меньше кода
Меньше памяти (n+1 вместо 4n)
Только префиксные суммы

Массив: [1, 3, 5, 7, 9, 11] Дерево отрезков (сумма): [0-5: 36] / \ [0-2: 9] [3-5: 27] / \ / \ [0-1: 4] [2-2: 5] [3-4: 16] [5-5: 11] / \ / \ [0-0:1] [1-1:3] [3-3:7] [4-4:9]

Задача

Segment Tree

Fenwick Tree

Prefix Sum

Naive

Сумма на отрезке

✅ O(log n)

✅ O(1)

❌ O(n)

Минимум на отрезке

✅ O(log n)

❌ Нет

❌ O(n)

Точечное обновление

✅ O(log n)

❌ O(n)

✅ O(1)

Универсальность

✅ Высокая

⚠️ Только сумма

❌ Низкая

✅ Любая

Простота реализации

⚠️ Средняя

✅ Простая

Ввод: ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] Вывод: [null, 9, null, 8] Объяснение: NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1, 2, 5] numArray.sumRange(0, 2); // 1 + 2 + 5 = 8

Массив: [1, 3, 5, 7, 9, 11] Построение дерева (сумма): [0-5: 36] / \ [0-2: 9] [3-5: 27] / \ / \ [0-1: 4] [2-2: 5] [3-4: 16] [5-5: 11] / \ / \ [0-0:1] [1-1:3] [3-3:7] [4-4:9] Каждый узел хранит сумму диапазона: - Листья: отдельные элементы - Внутренние узлы: сумма детей

Запрос sum(1, 4) для [1, 3, 5, 7, 9, 11]: [0-5: 36] / \ [0-2: 9] [3-5: 27] / \ / \ [0-1: 4] [2-2: 5] [3-4: 16] [5-5: 11] / \ / \ [0-0:1] [1-1:3] [3-3:7] [4-4:9] ↑ ↑ └─────── запрос [1,4] ──────┘ Разбиваем запрос: - [1,1]: берём [1-1:3] - [2,2]: берём [2-2:5] - [3,4]: берём [3-4:16] Сумма: 3 + 5 + 16 = 24

Ввод: nums = [5,2,6,1] Вывод: [2,1,1,0] Объяснение: 5: справа есть 2 и 1 (меньше) → 2 2: справа есть 1 (меньше) → 1 6: справа есть 1 (меньше) → 1 1: справа нет элементов → 0 Ввод: nums = [-1,-1] Вывод: [0,0]

Ввод: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Вывод: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] Ввод: buildings = [[0,2,3],[2,5,3]] Вывод: [[0,3],[5,0]]

Ввод: ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] Вывод: [null, null, null, true, false, true]

Задача

Структура

Ключевая идея

Range Sum Query

Segment Tree

update/query за O(log n)

Count Smaller

Fenwick + сжатие

Справа налево, query(rank-1)

Skyline

Heap + events

Max-heap активных зданий

Reverse Pairs

Merge Sort

Подсчёт во время слияния

Range Module

Список интервалов

Объединение/разбиение