Дерево отрезков для диапазонных запросов и обновлений. Сумма, минимум, максимум.
Дерево отрезков для диапазонных запросов (сумма, минимум, максимум) и обновлений. Построение O(n), запрос O(log n).
Segment Tree (Дерево отрезков) — это древовидная структура данных для эффективных диапазонных запросов и обновлений. Каждый узел дерева представляет отрезок массива и хранит агрегированное значение (сумму, минимум, максимум и т.д.).
Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.
Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.
Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.
Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.
Массив: [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 — для минимумов/максимумов и сложных операций.
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))Условие:
Реализуйте класс NumArray для работы с целочисленным массивом nums:
update(index, val) — обновляет значение nums[index] на valsumRange(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
Ограничения:
💡 Подсказка: Используйте 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)Объяснение:
Сложность:
Условие:
Дан целочисленный массив 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]
Ограничения:
💡 Подсказка: Используйте 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]Объяснение:
Сложность:
Условие:
Городская 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]]
Ограничения:
💡 Подсказка: Используйте 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Объяснение:
Сложность:
Условие:
Дан целочисленный массив nums. Верните количество reverse pairs, где:
0 <= i < j < nums.lengthnums[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)
Ограничения:
💡 Подсказка: Используйте модифицированную сортировку слиянием. Во время слияния считайте пары.
Решение:
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)Объяснение:
Сложность:
Условие:
Реализуйте класс 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]
Ограничения:
💡 Подсказка: Используйте отсортированный список непересекающихся интервалов. При добавлении объединяйте пересекающиеся.
Решение:
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)Объяснение:
Сложность:
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)| Задача | Структура | Ключевая идея |
|---|---|---|
| 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 | Список интервалов | Объединение/разбиение |
Проблема: Недостаточно памяти.
# ❌ Неправильно
self.tree = [0] * (2 * n) # Мало!
# ✅ Правильно
self.tree = [0] * (4 * n) # Достаточно для полного дереваПочему это неправильно: Для n элементов нужно до 4n узлов.
Проблема: Выход за границы.
# ❌ Неправильно
mid = (start + end) // 2 # Может переполниться!
# ✅ Правильно
mid = start + (end - start) // 2Почему это неправильно: Сумма может превысить max int.
Проблема: Бесконечная рекурсия.
# ❌ Неправильно
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.
Проблема: Неверные результаты.
# ❌ Неправильно
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]Почему это неправильно: Нужно проверять непересекающиеся диапазоны.
Проблема: Fenwick не поддерживает все операции.
# ❌ Неправильно — Fenwick для минимума
# Fenwick поддерживает только суммы!
# ✅ Правильно — Segment Tree для минимума/максимумаПочему это неправильно: Fenwick работает только с ассоциативными операциями типа суммы.
Условие: Реализуйте структуру данных для суммы диапазона с обновлением элемента.
Пример:
Ввод: ["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
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)Объяснение:
Сложность:
Segment Tree для сложных диапазонных запросов:
Fenwick Tree проще для сумм:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.