Основные структуры данных на Python

Привет! Представь, что у тебя есть поток чисел или коллекция слов, и нужно быстро отвечать на вопросы вроде «встречалось ли это слово раньше?» или «какой сейчас третий по счёту минимум?» Для этого существуют разные «строительные блоки» — структуры данных, каждая из которых даёт свою «скорость» поиска или вставки. В этом вводном уроке мы разберём, зачем нужно выбирать правильную структуру и как это отражается на производительности.

Что такое «O-большое» и зачем оно нужно

O-большое (произносится «О-большое») — это способ описать, как растёт время работы (или объём памяти) при увеличении размера входа.

Мы не смотрим на точные секунды (они зависят от компьютера и погоды!), а сравниваем масштаб:

• O(1) — константное время. Пример: нажатие Enter — мгновенно, независимо от количества введённых слов.
• O(n) — линейное время. Пример: перелистывание книги — чем больше страниц, тем дольше.
• O(log n) — логарифмическое время. Пример: поиск в телефонном справочнике методом «каждый раз делим список пополам».
• O(n log n) — типично для эффективных сортировок (QuickSort, TimSort).
• O(n²) — квадратичное время. Пример: проверка каждой пары учеников в классе (30×30 сравнений).

Важно: мы опускаем коэффициенты и мелкие детали («×2», «+100»), потому что при очень большом n они не меняют порядок роста.

Что значит «O(1) амортизированно»?

Когда мы говорим, что операция выполняется за O(1) амортизированно, мы имеем в виду, что в большинстве случаев она занимает одинаковое, маленькое время — «константу» — но иногда может потребоваться чуть больше усилий, и тогда она «дороже». Однако если усреднить время работы по многим операциям, то «дорогие» шаги бывают редко, и в среднем каждая операция всё равно остаётся «быстрой».

Аналогия: у тебя есть копилка, и ты кладёшь туда монеты. Большую часть раз ты просто бросаешь монету — это быстро. Иногда твоя мама вдруг захочет пересчитать все монеты — и тогда ты тратишь время. Но если смотреть на сотню бросков, подсчёт один раз не сильно скажется на среднем времени «одного броска». Вот это и есть «амортизированное O(1)» — в среднем за операцию платим константу.

Коротко о «скоростях» основных структур

Теперь — какие «скорости» дают самые популярные структуры в Python:

• list — элементы хранятся подряд в памяти:
  • Доступ по индексу: O(1)
  • Вставка или удаление в середине: O(n)
• collections.deque — двусторонняя очередь/стек, где можно извлекать и добавлять крайние элементы с двух сторон (сначала и с конца) Что такое очередь и стек, мы расскажем позже:
  • добавить/извлечь с начала или конца: O(1) амортизированно¹
  • Но произвольный доступ или поиск — O(n)
• dict / set — хеш-таблица:
  • Вставка, удаление, поиск ключа: O(1) в среднем²
• heapq — бинарная куча на массиве:
  • добавить/извлечь из кучи: O(log n)

¹ «Амортизированно» значит: иногда операция может быть дороже (например, расширение буфера), но в среднем выходит O(1).
² «В среднем» — при удачном распределении хешей; в худшем случае (много коллизий) может быть O(n).

Как работает куча (heapq)

Куча — это почти отсортированное бинарное дерево, где в корне всегда лежит или минимум (min-heap), или максимум (max-heap). В Python — min-heap.

      [ 2 ]
     /   \
   [5]   [8]
   / \   /
 [6] [9][7]

В памяти куча хранится в списке A так, что для индекса i:

• левый потомок — 2·i+1
• правый потомок — 2·i+2
• родитель — (i−1)//2

1. heappush(A, x) — вставляем x в конец списка, затем «всплываем» вверх: меняем местами с родителем, пока меньше.
2. heappop(A) — забираем корень (минимум), на его место ставим последний элемент списка, «опускаем» его вниз, меняя с меньшим из детей.

Эти «всплытие»/«опускание» дают сложность O(log n), потому что высота дерева ≈ log₂ n.

Примеры выбора структуры

🔹 Найти, встречалось ли слово раньше

• list: поиск O(n) — медленно при 50 000 слов.
• set: поиск O(1) в среднем — мгновенно.

🔹 Держать k наибольших элементов

• heapq: O(log k) при вставке — хорошо, если k≪n.
• sorted(list): O(n log n) — медленно для больших n.

1. В каких задачах пригодится deque?
2. Когда лучше словарь, а когда — куча?

1. Последовательности «из коробки»

► list — динамический массив

В Python list хранит элементы в одном непрерывном блоке памяти.

Когда вы добавляете элементы и достигаете текущей ёмкости (capacity), интерпретатор выделяет новый блок в два раза большего размера и копирует туда все ссылки, чтобы оставался запас места для роста.

Благодаря этому доступ по индексу остаётся мгновенным (O(1)), а добавление в конец — амортизированно O(1).

Однако вставка или удаление элемента в середине (или в начале) требует сдвига всех последующих ссылок — O(n). Поиск или удаление по значению тоже O(n). Если вам нужны частые вставки в произвольные позиции или быстрые проверки на вхождение без сдвига, стоит посмотреть в сторону deque, set или dict.

• Как растёт list (capacity):
  • Когда size == capacity, создаётся новый массив размером max(1, capacity×2), все элементы копируются, старая память освобождается.
  • В CPython напрямую capacity не доступна, но lst.__sizeof__() возвращает байты под внутренний массив — можно сравнить с len(lst).
• Сложность основных операций:
  • append(x) — O(1) амортизировано (редко O(n), когда нужен ресайз).
  • Доступ по индексу lst[i] — O(1).
  • Вставка/удаление в середине или начале — O(n) (из-за сдвига).
  • Поиск/удаление по значению — O(n) (линейный перебор).
  • lst += other — поэлементное добавление, O(len(other)).

   [ a | b | c | _ | _ ]   ← capacity = 5, size = 3
append(d) → [ a | b | c | d | _ ]   size = 4
append(e) → [ a | b | c | d | e ]   size = 5
append(f) → ресайз (×2):
[ a | b | c | d | e | _ | _ | _ ]   size = 6, capacity = 8

Пример: псевдокод append с ресайзом

# Python-подобный псевдокод 
def append(item): 
    if size == capacity: 
        new_cap = max(1, capacity*2) 
        new_arr = [None] * new_cap 
        for i in range(size): 
            new_arr[i] = arr[i] 
        arr = new_arr 
        capacity = new_cap 
    arr[size] = item 
    size += 1

Когда использовать:

• Нужен упорядоченный набор с быстрым доступом по индексу.
• Частые добавления в конец (append).
• Реализация стека (append/pop) или очереди (deque лучше для обеих сторон).

Когда не очень удобно:

• Частые вставки/удаления в середине/начале — выбирайте deque.
• Поиск по значению или гарантированно уникальный набор — выбирайте set или dict.

► tuple — неизменяемый упорядоченный контейнер

В Python tuple хранит элементы в одном непрерывном блоке памяти, как list, но после создания его нельзя изменить: добавить, удалить или присвоить по индексу. Благодаря этому tuple легче и компактнее по памяти, а операции неизменности делают их безопасными в многопоточном коде и пригодными для ключей в dict или элементов set.

Из-за неизменяемости:

• Доступ по индексу: O(1).
• Нельзя append, insert или pop — такие операции невозможны.
• Конкатенация a + b: O(len(a) + len(b)), создаётся новый tuple.
• Поиск x in tpl — O(n), линейный перебор.

  tpl = (a, b, c)
  // память: [ a | b | c ] — ровно size элементов, без запаса
  // попытка tpl[0] = x → TypeError: 'tuple' object does not support item assignment

Кэширование литерных кортежей

• CPython компилирует литералы (1, 2, 3) в константы — они хранятся в таблице констант модуля и переиспользуются при каждом обращении.
• Это экономит время и память при многократном использовании одних и тех же кортежей в коде.
• Однако динамически создаваемые кортежи не кешируются автоматически.

Когда использовать:

• Нужен неизменяемый упорядоченный набор.
• Хотите использовать последовательность как ключ в dict или элемент set.
• Заранее известное количество элементов и отсутствие мутаций.

Когда не очень удобно:

• Нужны частые изменения: выбирайте list или deque.
• Большие объединения: лучше собрать элементы в list и потом преобразовать в tuple.

Примеры

Простой: доступ и распаковка

tpl = (10, 20, 30)
print(tpl[1])         # 20, O(1)
a, b, c = tpl         # распаковка кортежа

Средний: ключи в словаре

points = {
    (0, 0): 'origin',
    (1, 2): 'point A',
}
print(points[(1, 2)]) # 'point A'

Сложный: объединение и неизменяемость

a = (1, 2)
b = (3, 4)
c = a + b           # новый кортеж (1,2,3,4), O(len(a)+len(b))
# a и b остались без изменений

► array.array — гомогенный компактный массив

array.array хранит элементы одного фиксированного типа (числа), упакованные без лишних ссылок. Это даёт меньший объём памяти по сравнению с list и более быструю сериализацию.

• Типы: 'b', 'i', 'f' и др. (см. документацию).
• Сложность операций:
  • Доступ по индексу a[i] — O(1).
  • append(x) — O(1) амортизированно.
  • Вставка/удаление в середине — O(n) (сдвиг памяти).
  • Поиск x in a — O(n).
• Когда использовать: большие числовые массивы, обмен бинарными данными, C-расширения.
• Когда не стоит: разнородные элементы, динамическое добавление разных типов — используйте list или numpy.ndarray.

   [ i0 | i1 | i2 | … ]   ← каждый элемент занимает одинаковый байт-размер
# Пример: массив 4-байтовых целых
from array import array
a = array('i', [10, 20, 30])
a.append(40)          # O(1)
print(a[2])           # 30, O(1)

► Почему array.array лучше для больших однородных данных чем list

Если у вас миллион одинаковых чисел, list хранит каждый элемент как отдельный объект с указателем, а array — просто подряд «сырые» числа. Это значит:

• Меньше памяти: нет лишних указателей и объектов.
• Быстрее запись/чтение на диск или сеть: можно сразу взять весь блок.

import sys
from array import array

# миллион нулей в list и в array
lst = [0] * 10**6
arr = array('i', [0] * 10**6)

print("list:",   sys.getsizeof(lst), "bytes")
print("array:",  sys.getsizeof(arr), "bytes")

На моей машине это даёт примерно:

list: 8697456 bytes  
array:  4000016 bytes  

Видно, что array почти вдвое компактнее.

► bytes — неизменяемая последовательность байтов

bytes хранит бинарные данные как подряд идущие байты без возможности изменения. Используется для сетевых протоколов, криптографии, работы с файлами.

• Сложность операций:
  • Доступ по индексу b[i] — O(1).
  • Срезы b[i:j] — O(k), создаётся новый bytes длины k.
  • Конкатенация b1 + b2 — O(len(b1)+len(b2)).
  • Поиск needle in haystack — O(n·m) (алгоритм поиска подстроки).
• Когда использовать: неизменяемые бинарные данные, ключи хеш-таблиц, константы.
• Когда не стоит: требуется изменение содержимого — используйте bytearray.

data = b'Hello, world!'
print(data[7])        # 119 (код 'w'), O(1)
chunk = data[0:5]     # b'Hello', O(5)
new = data + b'!!'    # b'Hello, world!!!', O(n)

► bytearray — изменяемая последовательность байтов

bytearray похож на bytes, но позволяет менять отдельные байты, добавлять и удалять. Под капотом тоже динамический массив байтов.

• Сложность операций:
  • Доступ и присвоение ba[i] — O(1).
  • append/extend — O(1) амортизированно.
  • Вставка/удаление середине — O(n).
  • Срезы и конкатенации — O(k) или O(n+m).
• Когда использовать: чтение/запись бинарных протоколов, формирование и изменение буферов.
• Когда не стоит: только чтение без изменений — проще bytes.

buf = bytearray(b'\x00\x01\x02')
buf[1] = 255           # O(1)
buf.append(3)          # O(1)
del buf[0]             # O(n): сдвиг байтов
print(buf)             # bytearray(b'\xff\x02\x03')

ASCII-иллюстрация памяти bytearray:
[ b0 | b1 | b2 | _ | _ ]   ← capacity = 5, size = 3
append(3) → [ b0 | b1 | b2 | 3 | _ ]   size = 4
append(4) → [ b0 | b1 | b2 | 3 | 4 ]   size = 5
append(5) → ресайз (×2):
[ b0 | b1 | b2 | 3 | 4 | _ | _ | _ ]   size = 6, capacity = 8

► Сравнительная таблица встроенных структур

1.1. Какие операции у list выполняются за O(1), а какие — за O(n)?

1.2. Почему кортеж (tuple) можно использовать в качестве ключа словаря, а список (list) — нет?

1.3. В чём разница между bytes и bytearray? Когда выбрать каждый из них?

1.4. Почему array.array занимает меньше памяти, чем list при хранении одинаковых чисел?

1.5. Для чего полезна неизменяемость tuple и bytes? Приведите пример использования.

Задания. Блок 1. Списки, кортежи и компактные массивы

1.1. list — «скользящий» буфер сообщений
Задание:
Напишите функцию
def add_message(buffer: list[str], msg: str, max_len: int) -> None:
которая добавляет msg в конец buffer и удаляет первый элемент, если длина превысила max_len.
❓ Почему удаление первого элемента стоит O(n)?

1.2. list — скользящие средние
Задание:
Реализуйте функцию
def sliding_avg(data: list[float], k: int) → list[float]:
которая для списка data=[1,2,3,4,5] и k=3 вернёт [2.0, 3.0, 4.0].
❓ Какова временная сложность этого алгоритма?

1.3. tuple — ключ для словаря
Задание:
Дан список координат:
coords = [(0,0), (1,2), (0,0), (2,1)]
Постройте словарь, где ключ — координата (tuple), а значение — число её вхождений.
❓ Почему именно tuple можно использовать ключом?

1.4. array.array — инверсия пикселей
Задание:
Есть список значений пикселей (0…255):
pixels = [12, 200, 34, 255, 0, 128]
Запишите их в array('B') и замените каждый элемент на 255 − x (инверсия цвета). Покажите код.
❓ Почему при большом числе пикселей array('B') лучше, чем list?

1.5. bytearray — правка текста в байтах
Задание:
Дана байтовая строка:
data = b"Error 404: Not Found"
Преобразуйте в bytearray, замените все пробелы на подчёркивания и верните результат в виде bytes.
❓ Почему такую правку нельзя сделать напрямую с bytes?

1.1.  
— append в конец: амортизированно O(1).  
— удаление первого элемента (pop(0)): O(n), т.к. после удаления все остальные сдвигаются на 1.

1.2.  
— Для каждого из N−k+1 окон по k элементов: O((N−k+1)·k) ≈ O(N·k). Если k≈N, то O(N²).

1.3.  
— Ключи словаря должны быть неизменяемыми и хешируемыми.  
— tuple неизменяем и имеет хеш, list изменяем и хеш не поддерживает.

1.4.  
— array('B') хранит «сырые» байты без лишних объектов и указателей, каждый элемент гарантированно 1 байт.  
— list хранит объекты int и указатели — ~28 байт на элемент.

1.5.  
— bytes — неизменяемый тип, нельзя менять содержимое по индексу.  
— bytearray — изменяемый буфер, позволяет править отдельные байты.

# 1.1. Скользящий буфер сообщений
def add_message(buffer: list[str], msg: str, max_len: int) -> None:
    buffer.append(msg)           # O(1) амортизированно
    if len(buffer) > max_len:
        buffer.pop(0)            # O(n): сдвиг всех элементов

# 1.2. Скользящие средние
def sliding_avg(data: list[float], k: int) -> list[float]:
    n = len(data)
    result = []
    for i in range(n - k + 1):   # O(n−k+1)
        window = data[i:i+k]     # O(k)
        result.append(sum(window) / k)  # O(k)
    return result

# 1.3. Словарь подсчёта координат
coords = [(0,0), (1,2), (0,0), (2,1)]
counts: dict[tuple[int,int], int] = {}
for pt in coords:               # O(n)
    counts[pt] = counts.get(pt, 0) + 1

# 1.4. Инверсия пикселей с array('B')
from array import array
pixels = [12, 200, 34, 255, 0, 128]
arr = array('B', pixels)        # каждый элемент 1 байт
for i in range(len(arr)):       # O(n)
    arr[i] = 255 - arr[i]       # O(1) присвоение
# arr теперь содержит инвертированные значения

# 1.5. Замена пробелов через bytearray
data = b"Error 404: Not Found"
buf = bytearray(data)           # копия в изменяемый буфер
for i in range(len(buf)):       # O(n)
    if buf[i] == 0x20:          # код пробела
        buf[i] = ord('_')       # заменить на '_'
result = bytes(buf)             # вернуть в bytes

Односвязный и двусвязный списки

Связный список — это последовательность узлов (элементов), где каждый узел хранит само значение и «указатель» на следующий (и, в случае двусвязного, ещё и на предыдущий) узел. Указатель — это просто ссылка или адрес, по которому хранится следующий элемент.

Зачем это нужно? В обычном списке (list) вставка или удаление в середине требует сдвига всех элементов. В связном списке достаточно перенастроить указатели. Знание этих структур помогает понимать, как устроены более сложные алгоритмы и оптимизировать память и скорость там, где это важно.

Односвязный список (Singly Linked List)

[Head] → [ A | next ] → [ B | next ] → [ C | next ] → None

• Получить i-й элемент: пройти по next i раз — O(i).
• Вставка в середину: перенаправить «next» предыдущего узла на новый, а новый — на старый следующий — O(1).
• Удаление в середине: предыдущий узел «next» = узел.next.next — O(1).
• Вставка в конец: либо хранить tail, либо пройти до конца O(n), затем добавить новый узел и обновить tail.
• Смена мест двух узлов: перенастроить соседние указатели вокруг них (несколько O(1) операций, но нужно знать предыдущие узлы).

# Вставка узла X между A и B:
A.next → X
X.next → B

# Удаление узла B (между A и C):
A.next → C

Двусвязный список (Doubly Linked List)

None ← [prev | A | next] ←→ [prev | B | next] ←→ [prev | C | next] → None

• Каждый узел хранит prev (ссылку на предыдущий) и next.
• Получить предыдущий элемент за O(1) — удобно для обхода в обе стороны.
• Вставка/удаление узла X между A и B:

# Вставка X между A и B:
X.prev → A
X.next → B
A.next → X
B.prev → X

# Удаление X:
A = X.prev
B = X.next
A.next → B
B.prev → A

Реализация в Python

class SinglyNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        node = SinglyNode(value)
        if not self.head:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def insert_after(self, prev_node, value):
        if not prev_node: return
        node = SinglyNode(value)
        node.next = prev_node.next
        prev_node.next = node

    def delete_after(self, prev_node):
        if not prev_node or not prev_node.next: return
        prev_node.next = prev_node.next.next

    def get(self, index):
        cur = self.head
        for _ in range(index):
            if not cur: return None
            cur = cur.next
        return cur.value if cur else None

class DoublyNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = DoublyNode(value)
        if not self.head:
            self.head = self.tail = node
            return
        self.tail.next = node
        node.prev = self.tail
        self.tail = node

    def insert_after(self, node, value):
        if not node: return
        new = DoublyNode(value)
        nxt = node.next
        node.next = new
        new.prev = node
        new.next = nxt
        if nxt:
            nxt.prev = new
        else:
            self.tail = new

    def delete(self, node):
        if not node: return
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def get(self, index):
        cur = self.head
        for _ in range(index):
            if not cur: return None
            cur = cur.next
        return cur.value if cur else None

Почему в Python редко делают так вручную?

• Встроенный list и deque работают на C, очень оптимизированы и быстрее нашего Python-кода.
• Дополнительные объекты узлов и ссылки занимают больше памяти и замедляют работу интерпретатора.
• Тем не менее, понимание связных списков помогает при изучении алгоритмов, низкоуровневых реализаций и работы памяти «под капотом».

2.1. В чем разница между односвязным и двусвязным списком? Какой из них требует больше памяти на узел и почему?

2.2. Какие операции в связном списке выполняются за O(1), а какие — за O(n)? Приведите примеры.

2.3. Что такое «указатель» (pointer) в контексте связного списка, и зачем он нужен?

2.4. Почему при удалении узла в середине односвязного списка нужно знать предыдущий узел? Как этого избежать?

2.5. Как реализовать проверку на наличие цикла в связном списке без использования дополнительной памяти?

Задания. Блок 2. Связные списки

2.1. Создание и обход
Задание:
Реализуйте односвязный список с методами `append(value)` и `to_list()`, который возвращает все значения в виде Python-списка.
❓ Какова сложность метода `to_list()`?

2.2. Реверс односвязного списка
Задание:
Напишите метод `reverse()` для вашего односвязного списка, который меняет порядок узлов на обратный, не создавая новые узлы.
❓ Почему алгоритм выполняется за O(n) и O(1) дополнительной памяти?

2.3. Удаление по значению
Задание:
Добавьте в односвязный список метод `remove(value)`, который удаляет первый узел с указанным значением. Учтите крайние случаи (пустой список, удаление головы).
❓ Какой указатель необходимо обновить при удалении головы?

2.4. Объединение списков
Задание:
Даны два отсортированных односвязных списка. Реализуйте функцию `merge(l1, l2)`, которая сливает их в один отсортированный список, не создавая новых узлов.
❓ Почему этот алгоритм идёт за O(n₁ + n₂)?

2.5. Двухсвязный список: вставка и удаление
Задание:
Реализуйте двусвязный список с полями `head`, `tail` и методами `insert_after(node, value)` и `delete(node)`.
❓ Какие указатели нужно переназначить при удалении узла из середины?

Стек и очередь

Стек (stack) и очередь (queue) — базовые линейные структуры данных:

• Стек — «последний зашёл — первый вышел» (LIFO). Представьте стопку тарелок: кладёте сверху, берёте тоже с верха.
• Очередь — «первый зашёл — первый вышел» (FIFO). Представьте очередь в кассу: первый пришёл — первым обслужили.

Аналогии из реальной жизни

• Стек: стопка тарелок, отмена действий в текстовом редакторе (undo).
• Очередь: очередь в магазине, печать документов в принтере.

Как это работает

Стек (push/pop):
[ ]      ← пустой
push(1) → [ 1 ]
push(2) → [ 1, 2 ]
pop()   → [ 1 ]  returns 2

Очередь (enqueue/dequeue):
[ ]      ← пустая
enq(1) → [ 1 ]
enq(2) → [ 1, 2 ]
deq()  → [   2 ] returns 1

В Python

• Стек: можно на list (append/pop) или лучше на collections.deque.
• Очередь: collections.deque или queue.Queue (для многопоточности).
• Почему deque лучше list: оба конца O(1) при вставке/удалении, тогда как list.pop(0) — O(n).

Пример реализации с deque

from collections import deque

# Стек
stack = deque()
stack.append(1)     # O(1)
stack.append(2)
print(stack.pop())  # 2, O(1)

# Очередь
queue = deque()
queue.append(1)     # enqueue O(1)
queue.append(2)
print(queue.popleft())  # 1, dequeue O(1)

Когда использовать

• Стек: обход графа в глубину (DFS), отмена операций, разбор выражений.
• Очередь: обход графа в ширину (BFS), буферы задач, очереди сообщений.
• Не подходит, если нужна быстрое случайное удаление в середине.

Практические примеры

Практические задачи и подход к их решению

1. Поиск максимума в скользящем окне
   Дана последовательность чисел nums и окно размера k. Нужно для каждого положения окна найти его максимум.
   Подход: используем deque как «монотонную очередь» — будем хранить в ней индексы элементов так, чтобы значения в них шли по убыванию. При сдвиге окна удаляем из головы устаревшие индексы и из хвоста все меньшие нового элемента.
2. Вывод последних N строк лога
   Дан текстовый лог-файл, нужно вернуть его последние n строк без чтения всего файла в память.
   Подход: используем deque с параметром maxlen=n. По мере чтения добавляем строки в очередь, старые автоматически удаляются.
3. Проверка правильности скобочной последовательности
   Дано выражение, состоящее из скобок ()[]{}. Нужно проверить, что скобки правильно открываются и закрываются.
   Подход: используем stack (реализованный на deque). При открывающей скобке — кладём в стек, при закрывающей — проверяем соответствие с вершиной стека.
4. Топологическая сортировка графа
   Даны задачи (вершины) и зависимости между ними (ориентированные рёбра). Нужно найти порядок выполнения так, чтобы все зависимости соблюдались.
   Подход: считаем для каждой вершины число входящих рёбер (in-degree) и помещаем все вершины с нулевым in-degree в queue (deque). Далее по алгоритму Кана: извлекаем из очереди, уменьшаем in-degree соседей, добавляем в очередь вновь освободившиеся вершины.

1. «Скользящее окно» (sliding window)

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # хранит индексы, элементы — убывающие
    res = []
    for i, x in enumerate(nums):
        # убрать из головы, вышедшие за окно
        if dq and dq[0] <= i - k:
            dq.popleft()
        # убрать все меньшие, чем новый
        while dq and nums[dq[-1]] < x: dq.pop() dq.append(i) if i >= k - 1:
            res.append(nums[dq[0]])
    return res

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# → [3, 3, 5, 5, 6, 7]

2. Логи с ограничением размера

from collections import deque

def tail(filename, n=10):
    buf = deque(maxlen=n)
    with open(filename, 'r') as f:
        for line in f:
            buf.append(line.rstrip())
    return list(buf)

# buf хранит только последние n строк, автоматически сбрасывая старые

3. Синтаксический разбор скобок

def is_valid(expr):
    stack = deque()
    pairs = {'(':')', '[':']', '{':'}'}
    for ch in expr:
        if ch in pairs:
            stack.append(ch)
        elif ch in pairs.values():
            if not stack or pairs[stack.pop()] != ch:
                return False
    return not stack

print(is_valid("({[]})"))  # True
print(is_valid("([)]"))    # False

4. Топологическая сортировка (асинхронный граф)

Задача: есть набор задач (вершин) и зависимости (ребра):

   A → B → D
   ↓       ↑
   C -------

Нужно найти порядок выполнения так, чтобы все зависимости соблюдены (топологическая сортировка).

Что сделать:

1. Подсчитать для каждой вершины число входящих рёбер (in-degree).
2. Положить все вершины с in-degree=0 в очередь.
3. Удалять из очереди, добавлять в результат и уменьшать in-degree у соседей, добавляя новые с 0 в очередь.

from collections import deque, defaultdict

def topo_sort(edges):
    g = defaultdict(list)
    indeg = defaultdict(int)
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1
        indeg.setdefault(u, 0)
    q = deque([u for u in indeg if indeg[u]==0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order

edges = [('A','B'),('A','C'),('B','D'),('C','D')]
print(topo_sort(edges))  # Напр., ['A','B','C','D'] или ['A','C','B','D']

3.1. В чём основное отличие стека (LIFO) от очереди (FIFO)? Приведите по одному примеру из реальной жизни для каждого.

3.2. Какие методы у deque выполняют вставку и удаление за O(1)? Какие аналоги есть у list и какова их сложность?

3.3. Почему для реализации очереди лучше использовать deque, а не list? Что происходит при list.pop(0)?

3.4. Как стек используется при проверке правильности скобочной последовательности? Опишите алгоритм.

3.5. Как очередь помогает при обходе графа в ширину (BFS)? Что хранят в очереди и как обновляется состояние?

Задания. Блок 3. Стек и очередь

3.1. Разворот строки через стек
Задание:
Напишите функцию
def reverse_str(s: str) -> str:
которая с помощью стека (deque) переворачивает строку.
❓ Какова временная сложность алгоритма?

3.2. Вычисление постфиксного выражения
Задание:
Напишите функцию
def eval_postfix(tokens: list[str]) -> int:
которая на основе стека вычисляет значение выражения в обратной польской нотации, например ["3","4","+","2","*"] → 14.
❓ Почему для этого удобно использовать стек?

3.3. Симуляция планировщика (round-robin)
Задание:
Есть список процессов ["P1","P2","P3"] и квант 1 (единица работы). Симулируйте исполнение: каждый раз берём из очереди процесс, «отрабатываем» квант, если ему осталось больше нуля — возвращаем в очередь с уменьшённым временем. Верните порядок выполнения.
❓ Какой метод очереди позволяет удалить и сразу получить элемент?

3.4. Поиск кратчайшего пути в сетке
Задание:
Дана матрица 0 и 1, 0 — проходимая клетка, 1 — стена. Найдите длину кратчайшего пути от (0,0) до (n−1,m−1) по 4-м направлениям, или верните −1, если пути нет.
❓ Как с помощью очереди обеспечить обход в ширину?

3.5. Обход каталогов (DFS)
Задание:
Симулируйте обход файловой системы: у вас словарь, где ключ — имя папки, значение — список файлов и подпапок. Используя стек, верните список всех файлов в порядке глубокого обхода.
❓ Почему стек позволяет реализовать DFS без рекурсии?

3.1. Для "hello" результат → "olleh".  
3.2. ["3","4","+","2","*"] → 14.  
3.3. При P1:2, P2:3, P3:1 (например), порядок → ["P1","P2","P3","P1","P2",...].  
3.4. В простом случае (2×2 без стен) путь = 3 шага или -1.  
3.5. Список всех файлов в глубину, например ["f1","f2","f3",...].

# 3.1. reverse_str
def reverse_str(s: str) -> str:
    stack = deque(s)
    res = []
    while stack:
        res.append(stack.pop())
    return ''.join(res)

# 3.2. eval_postfix
def eval_postfix(tokens: list[str]) -> int:
    stack = deque()
    for t in tokens:
        if t.isdigit():
            stack.append(int(t))
        else:
            b, a = stack.pop(), stack.pop()
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            elif t == '/': stack.append(int(a / b))
    return stack.pop()

# 3.3. round-robin scheduler
def rr_schedule(procs: dict[str,int]) -> list[str]:
    q = deque((name for name in procs))
    order = []
    while q:
        p = q.popleft()
        procs[p] -= 1
        order.append(p)
        if procs[p] > 0:
            q.append(p)
    return order

# 3.4. BFS shortest path in grid
def shortest_path(grid: list[list[int]]) -> int:
    n, m = len(grid), len(grid[0])
    q = deque([ (0,0,0) ])  # x,y,dist
    seen = {(0,0)}
    while q:
        x,y,d = q.popleft()
        if (x,y) == (n-1,m-1):
            return d
        for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x+dx, y+dy
            if 0<=nx list[str]:
    stack = deque([('', node) for node in tree['/']])
    files = []
    while stack:
        path, name = stack.pop()
        full = f"{path}/{name}"
        if name in tree:  # папка
            for child in tree[name]:
                stack.append((full, child))
        else:
            files.append(full)
    return files
# 3.5. DFS directory traversal
def dfs_files(tree: dict[str,list[str]]) -> list[str]:
    stack = deque([('', node) for node in tree['/']])
    files = []
    while stack:
        path, name = stack.pop()
        full = f"{path}/{name}"
        if name in tree:  # папка
            for child in tree[name]:
                stack.append((full, child))
        else:
            files.append(full)
    return files

Хэш-структуры

Хэш — это число-отпечаток, которое получается из данных (строки, числа и т.п.) с помощью специальной функции (hash-функции).

Оно используется как «адрес» для быстрого хранения и поиска.

Хэш-таблица — это как почтовые ящики: у каждого ключа есть свой номер (hash), и по этому номеру мы сразу находим ящик, где хранится значение.

      +--------+--------+--------+  
 hash | bucket | bucket | bucket |  …  
      +--------+--------+--------+  
        ↓   ↑      ↓   ↑      ↓   ↑
      [k:v]      [ ]      [k:v]
       (1)                (2)

 1) Ключ k попал в bucket по hash(k)
 2) Если несколько ключей попали в один bucket, они складываются в список внутри этого bucket

Словарь (dict)

• Что хранит: пары «ключ → значение».
• Бакеты: внутрь каждой «ячейки» (bucket) помещается одна или несколько пар в случае коллизий.
• Требования к ключу: должен быть неизменяемым и хешируемым (строка, число, кортеж из хешируемых и т.п.).
• Скорость операций:
  • Поиск по ключу — O(1) в среднем.
  • Добавление/удаление — O(1) в среднем.
  • В худшем случае (много коллизий) — O(n).
• Преимущества: быстрый доступ по ключу, понятный синтаксис.
• Ограничения: ключи должны быть хешируемыми, большой размер → больше памяти.
• Порядок вставки: с Python 3.7 словари сохраняют порядок добавления ключей.
• Когда использовать: связывать данные по уникальному ключу, строить индексы, кэшировать результаты.

Примеры работы со словарём

# Создание и базовые операции
d = {}                           # пустой словарь
d['Alice'] = 25                  # добавить пару
d['Bob'] = 30
print(d['Alice'])                # → 25
print('Eve' in d)                # → False

# Перебор ключей и значений
for name, age in d.items():
    print(name, age)

# Получение с умолчанием
print(d.get('Eve', 0))           # → 0

# Удаление
d.pop('Bob')                     # удаляет и возвращает 30

# Инициализация из списка пар
pairs = [('x', 1), ('y', 2)]
d2 = dict(pairs)

Множество (set) и неизменяемое множество (frozenset)

• Что хранит: набор уникальных хешируемых элементов (ключи без значений).
• Как хэши применяются: элемент попадает в bucket по своему hash; коллизии обрабатываются списком внутри bucket.
• Скорость операций:
  • Проверка вхождения — O(1) в среднем.
  • Добавление/удаление — O(1) в среднем.
  • Объединение, пересечение, разность множеств — O(n) в зависимости от размера.
• Преимущества: быстрое проверка уникальности, операции над множествами.
• Ограничения: только хешируемые элементы, большие объёмы данных требуют больше памяти.
• Когда использовать: удаление дубликатов, тест «вхождения», операции пересечений (поиск общих элементов).

Примеры работы с set и frozenset

# set — изменяемое множество
s = {1, 2, 3}
s.add(4)                # → {1,2,3,4}
s.remove(2)             # → {1,3,4}
print(3 in s)           # → True

# Операции над множествами
a = {1,2,3}
b = {2,3,4}
print(a & b)            # пересечение → {2,3}
print(a | b)            # объединение  → {1,2,3,4}
print(a - b)            # разность    → {1}

# frozenset — неизменяемый аналог
fs = frozenset([1,2,2,3])
# fs.add(4) → AttributeError, нельзя менять
print(fs)               # → frozenset({1,2,3})

Практические задачи с dict и set

1. Подсчёт частоты слов
   Постановка: дана строка текста. Нужно узнать, сколько раз встретилось каждое слово.
   Алгоритм:
   1. Разбить текст по пробелам и знакам пунктуации.
   2. Для каждого слова увеличить счётчик в словаре freq: freq[word] = freq.get(word, 0) + 1.
   3. Вернуть получившийся словарь.
2. Поиск общих уникальных элементов
   Постановка: даны два списка чисел. Нужно вернуть все числа, которые встречаются и в первом, и во втором, без повторов.
   Алгоритм:
   1. Преобразовать каждый список в множество.
   2. Взять пересечение: set1 &set2.
   3. Вернуть результат (можно как список).
3. Группировка анаграмм
   Постановка: дана коллекция слов. Нужно сгруппировать их по анаграммам (слова, содержащие одни и те же буквы).
   Алгоритм:
   1. Создать словарь groups, где ключ — отсортированная буква слова (''.join(sorted(w))), а значение — список слов.
   2. Для каждого слова добавить в groups[key].
   3. Вернуть список групп (groups.values()).
4. Рекомендация друзей (friends-of-friends)
   Постановка: у каждого пользователя есть множество друзей. Для данного пользователя найти тех, кто не в его друзьях, но является другом его друзей.
   Алгоритм:
   1. Объединить множества друзей всех его друзей.
   2. Удалить из полученного множества самого пользователя и его прямых друзей.
   3. Результат — множество рекомендаций.
5. Проверка орфографии
   Постановка: дана коллекция слов из текста и набор правильных слов (словарь). Нужно найти все уникальные слова, отсутствующие в словаре.
   Алгоритм:
   1. Преобразовать список слов текста в множество (unique_words).
   2. Вычесть множество словаря: unique_words - dict_set.
   3. Вернуть получившееся множество опечаток.

Решения

# 1. Подсчёт частоты слов
import re

def word_freq(text: str) -> dict[str,int]:
    words = re.findall(r"\\b\\w+\\b", text.lower())
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    return freq

# 2. Общие уникальные элементы
def common_unique(a: list[int], b: list[int]) -> set[int]:
    return set(a) & set(b)

# 3. Группировка анаграмм
from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

# 4. Рекомендация друзей
def recommend_friends(user: str, friends: dict[str,set[str]]) -> set[str]:
    direct = friends.get(user, set())
    fof = set()
    for f in direct:
        fof |= friends.get(f, set())
    return fof - direct - {user}

# 5. Проверка орфографии
def spell_check(text_words: list[str], dict_words: set[str]) -> set[str]:
    unique_words = set(w.lower() for w in text_words)
    return unique_words - dict_words

# Примеры вызова:
if __name__ == "__main__":
    txt = "Hello, hello world! This is a test. Test this."
    print(word_freq(txt))
    print(common_unique([1,2,3,2], [2,3,4]))
    print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
    friends_map = {
        "Alice": {"Bob","Carol"},
        "Bob": {"Alice","Dave"},
        "Carol": {"Alice","Eve"},
        "Dave": {"Bob"},
        "Eve": {"Carol"}
    }
    print(recommend_friends("Alice", friends_map))
    words = ["Ths","is","a","test","Test","this"]
    dict_set = {"this","is","a","test"}
    print(spell_check(words, dict_set))

4.1. Почему ключи в словаре должны быть неизменяемыми? Что произойдёт, если попытаться использовать изменяемый объект как ключ?

4.2. Что такое коллизия в хэш-таблице и как Python её обрабатывает?

4.3. Каково среднее и худшее время операций чтения, записи и удаления в dict и set?

4.4. Почему frozenset можно использовать как ключ словаря, а set — нет?

4.5. Как сохраняется порядок элементов в современном словаре Python? С какого релиза это гарантировано?

Задания. Блок 4. Хэш-структуры

4.1. Частотный словарь
Постановка: дана строка с текстом. Постройте словарь, где ключ — слово, значение — число его вхождений, игнорируя регистр и знаки пунктуации.
❓ Почему для подсчёта частот удобно использовать метод dict.get(key, 0)?

4.2. Инвертированный индекс
Постановка: есть список документов (каждый — строка). Нужно создать словарь, где ключ — слово, а значение — множество индексов документов, в которых это слово встречается.
❓ Почему здесь пригодится setdefault или defaultdict(set)?

4.3. Поиск дубликатов
Постановка: дан список чисел. Нужно вернуть новый список без дубликатов, сохранив порядок первого появления.
❓ Как сочетание set и list помогает это сделать?

4.4. Кэш результата функции
Постановка: напишите декоратор @memoize, который кэширует результаты вызова функции с неизменяемыми аргументами, используя словарь.
❓ Как сформировать ключ для аргументов функции?

4.5. Группировка по множеству тегов
Постановка: есть словарь items: dict[int, set[str]] — ключ ID, значение набор тегов. Нужно перевернуть структуру: получить словарь, где ключ — тег, а значение — множество ID, у которых есть этот тег.
❓ Почему при группировке удобно использовать defaultdict(set)?

4.1. Для неизменяемости и стабильности хэша: mutable-объект не имеет постоянного hash → TypeError.

4.2. Коллизия — два ключа с одинаковым hash попадают в один бакет. Python проверяет их по == и хранит в списке в этом бакете.

4.3. dict/get/set операций:  
    • Среднее чтение/запись/удаление — O(1)  
    • Худшее при коллизиях — O(n)

4.4. frozenset неизменяем и хешируем → можно использовать как ключ; set изменяем и не хешируется.

4.5. С Python 3.7 словари сохраняют порядок вставки (раньше это было implementation detail в CPython 3.6).

import re
from collections import defaultdict
from functools import wraps

# 4.1. Частотный словарь
def word_freq(text: str) -> dict[str,int]:
    words = re.findall(r"\b\w+\b", text.lower())
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    return freq

# 4.2. Инвертированный индекс
def inverted_index(docs: list[str]) -> dict[str,set[int]]:
    idx = defaultdict(set)
    for i, doc in enumerate(docs):
        for w in re.findall(r"\b\w+\b", doc.lower()):
            idx[w].add(i)
    return dict(idx)

# 4.3. Поиск дубликатов, сохранение порядка
def unique_in_order(seq: list[int]) -> list[int]:
    seen = set()
    result = []
    for x in seq:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

# 4.4. Декоратор memoize
def memoize(func):
    cache = {}
    @wraps(func)
    def wrapper(*args, **kwargs):
        key = args + tuple(sorted(kwargs.items()))
        if key not in cache:
            cache[key] = func(*args, **kwargs)
        return cache[key]
    return wrapper

# 4.5. Группировка по тегам
def group_by_tag(items: dict[int,set[str]]) -> dict[str,set[int]]:
    tag_map = defaultdict(set)
    for item_id, tags in items.items():
        for tag in tags:
            tag_map[tag].add(item_id)
    return dict(tag_map)

# Пример вызова:
if __name__ == "__main__":
    text = "Hello, world! Hello Python."
    print(word_freq(text))
    docs = ["The quick brown fox", "Quick fox jumps", "Lazy dog"]
    print(inverted_index(docs))
    print(unique_in_order([1,2,1,3,2,4]))
    @memoize
    def fib(n):
        return n if n < 2 else fib(n-1) + fib(n-2)
    print(fib(10))
    items = {1: {"a","b"}, 2: {"b","c"}, 3: {"a"}}
    print(group_by_tag(items))

Приоритетные очереди и кучи

Куча (heap) — это структура данных, которая позволяет быстро получать самый «важный» элемент (минимальный или максимальный).

Представьте кучу книг, где самая лёгкая всегда сверху (min-heap) или самая тяжёлая сверху (max-heap). Доступ к этому «верхнему» элементу — O(1), а вставка и удаление занимают O(log n).

Как устроена куча

Куча хранится как почти полное бинарное дерево, но под капотом — простой массив. Для узла с индексом i в массиве:

• Левый ребёнок — 2*i + 1
• Правый ребёнок — 2*i + 2
• Родитель — (i-1)//2

Индекс в массиве:     0   1   2   3   4   5   6
Позиция в дереве:
           [0]
         /     \
      [1]       [2]
     /   \     /   \
   [3]  [4] [5]   [6]

Вставка (push) нового элемента

1. Вставляем элемент в конец массива (новый лист).
2. «Всплываем» его вверх: сравниваем с родителем и меняем местами, если нарушает порядок (для min-heap — если меньше родителя).
3. Повторяем до тех пор, пока порядок не восстановится или не дойдём до корня.

Пример вставки 2 в min-heap [1, 3, 4, 7, 6]:
Массив: [1,3,4,7,6] → добавить 2 → [1,3,4,7,6,2]

Индекс 5: родитель = (5-1)//2 = 2 (значение 4)
2 < 4 → поменять местами:
[1,3,2,7,6,4]

Индекс теперь 2: родитель = (2-1)//2 = 0 (значение 1)
2 ≥ 1 → готово. 

Удаление (pop) «верхнего» элемента

1. Берём корень (самый важный элемент) для возвращения.
2. Последний элемент массива копируем в корень.
3. «Просеиваем» этот элемент вниз: сравниваем с детьми, меняем с меньшим (в min-heap), пока порядок не восстановится или нет детей.

Удаляем 1 из [1,3,2,7,6,4]:
1. Забираем 1.
2. Последний = 4 → ставим в корень: [4,3,2,7,6]
3. Сравниваем 4 с детьми 3 и 2 → 2 меньше → меняем с 2:
   [2,3,4,7,6]
4. Теперь индекс 2: дети нет или 7,6 — оба ≥ 4 → готово.

Каждое «всплытие» или «просеивание» перемещается по высоте дерева — O(log n). Поэтому вставка и удаление работают за O(log n).

Куча в Python

В стандартной библиотеке есть модуль heapq, который реализует min-heap поверх списка:

import heapq

heap = []
for x in [5, 1, 7, 3]:
    heapq.heappush(heap, x)    # вставить x
print(heap)                    # [1, 3, 7, 5]

smallest = heapq.heappop(heap) # удалить и вернуть минимальный
print(smallest, heap)          # 1, [3, 5, 7]

Min-heap и Max-heap

• Min-heap: корень — наименьший элемент.
• Max-heap: корень — наибольший элемент.

В Python max-heap можно эмулировать, вставляя отрицательные числа или используя обёртки:

# Вариант 1: отрицание
import heapq
nums = [5,1,7,3]
heap = []
for x in nums:
    heapq.heappush(heap, -x)
print(-heapq.heappop(heap))  # 7

# Вариант 2: кортеж с приоритетом
heap = []
for x in nums:
    heapq.heappush(heap, (-x, x))  # (-priority, value)
_, max_val = heapq.heappop(heap)
print(max_val)                  # 7

Скорость и применение

• Доступ к корню: O(1)
• Вставка: O(log n)
• Удаление корня: O(log n)

Преимущества: быстрое получение экстремального элемента, удобно для приоритетных очередей, алгоритмов Дейкстры, слияния K отсортированных списков.

Ограничения: нет быстрого поиска произвольного элемента, нет удаления не-корневого без O(n) поиска, требует O(n) памяти.

Слияние отсортированных последовательностей: heapq.merge()

Вместо того чтобы складывать два уже отсортированных списка и затем запускать sort() (O(n log n)), можно воспользоваться heapq.merge(), которое делает «k-путевое» слияние за O(n log k), где:

• n — общее число элементов во всех входных итераторах;
• k — число последовательностей.

Для двух списков (k=2) это приводит к O(n log 2) ≈ O(n) — значительно быстрее, чем O(n log n).

Как это работает

1. Из каждого входного итератора берётся первый элемент и помещается в вспомогательную «кучу» (heap) вместе с идентификатором источника.
2. Из кучи извлекается наименьший элемент и возвращается пользователю.
3. Из того же источника подставляют следующий элемент, и он «всплывает» в куче на своё место.
4. Повторяем до исчерпания всех элементов.

import heapq

a = [1, 3, 5]
b = [2, 4, 6]
# Результат: 1,2,3,4,5,6
merged = heapq.merge(a, b)
for x in merged:
    print(x)

• Скорость: O(n log k) для k входных потоков. При k=2 это близко к O(n).
• Память: O(k) для хранения текущих «голов» каждого итератора.
• Преимущество: не требует полной сортировки объединённого списка и работает лениво (порождает элементы по мере запроса).

Практические задачи с кучей

1. Топ-K наименьших элементов
   Постановка: дан большой список чисел, найдите K самых маленьких элементов.
   Алгоритм:
   • Построить max-кучу размера K из первых K элементов (храним отрицательные или используем обратный приоритет).
   • Для каждого оставшегося элемента x:
     • Если x < корня кучи, заменить корень на x (heapreplace), иначе — пропустить.
   • В конце корни кучи — ваши K наименьших элементов.
2. Топ-K наибольших элементов
   Постановка: аналогично, но нужно K самых больших чисел.
   Алгоритм:
   • Использовать min-кучу размера K.
   • Для каждого x: если x > корня → heapreplace, иначе — пропустить.
3. Слияние K отсортированных списков
   Постановка: дано несколько уже отсортированных списков, нужно получить единый отсортированный список.
   Алгоритм:
   • Воспользоваться heapq.merge() — ленивое k-путевое слияние за O(N log K).
4. Поиск медианы в потоке данных
   Постановка: поступают числа, после каждого числа нужно быстро отдавать текущую медиану.
   Алгоритм:
   • Две кучи: max-куча для «левой» половины и min-куча для «правой». Разница их размеров ≤1.
   • При добавлении числа x:
     • Если x ≤ корня max-кучи → в max-кучу, иначе → в min-кучу.
     • Если размеры отличаются более чем на 1, перекладываем элемент из одной кучи в другую.
   • Медиана = корень большей кучи или среднее двух корней, если размеры равны.
5. Алгоритм Дейкстры
   Постановка: в ориентированном графе с неотрицательными весами найти кратчайшие пути от стартовой вершины до всех остальных.
   Алгоритм:
   • Инициализировать расстояния: 0 для стартовой, ∞ для остальных.
   • Поставить в min-кучу пару (0, start).
   • Пока куча не пуста:
     • Извлечь вершину u с минимальным расстоянием d.
     • Если d > уже записанного расстояния[u], пропустить.
     • Для каждого соседа v с весом w:
       • Если d + w < расстояние[v], обновить и запушить (d+w, v).

Решения

import heapq
from typing import List, Tuple
from collections import defaultdict

# 1. Топ-K наименьших
def k_smallest(nums: List[int], k: int) -> List[int]:
    if k <= 0: return [] # max-куча через хранение отрицательных heap = [-x for x in nums[:k]] heapq.heapify(heap) for x in nums[k:]: if -x > heap[0]:
            heapq.heapreplace(heap, -x)
    return [-y for y in heap]

# 2. Топ-K наибольших
def k_largest(nums: List[int], k: int) -> List[int]:
    if k <= 0: return [] heap = nums[:k] heapq.heapify(heap) for x in nums[k:]: if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap

# 3. Слияние K списков
def merge_sorted(lists: List[List[int]]) -> List[int]:
    return list(heapq.merge(*lists))

# 4. Медиана в потоке
class MedianFinder:
    def __init__(self):
        self.lo = []  # max-куча (отрицательные)
        self.hi = []  # min-куча

    def add_num(self, num: int) -> None:
        if not self.lo or num <= -self.lo[0]: heapq.heappush(self.lo, -num) else: heapq.heappush(self.hi, num) # балансировка if len(self.lo) - len(self.hi) > 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) - len(self.lo) > 1:
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        if len(self.hi) > len(self.lo):
            return self.hi[0]
        return (-self.lo[0] + self.hi[0]) / 2

# 5. Алгоритм Дейкстры
def dijkstra(graph: dict[int, List[Tuple[int,int]]], start: int) -> dict[int,int]:
    dist = {u: float('inf') for u in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

5.1. Что такое min-heap и max-heap? Какое свойство выполняется для дочерних узлов?

5.2. Почему вставка и удаление в куче имеют сложность O(log n)?

5.3. Как связаны индексы массива и позиции узлов в двоичной куче?

5.4. Как в Python получить max-heap, если стандартный модуль реализует только min-heap?

5.5. В каких задачах применение кучи даёт улучшение по сравнению с простым сортированием?

Задания. Блок 5. Кучи

5.1. Построение кучи
Задание:
Напишите функцию
def build_heap(nums: list[int]) → list[int]:
которая превращает произвольный список в min-heap, используя heapq.heapify и возвращает этот список.
❓ После вызова heapify выполнение какого свойства гарантируется для каждого узла?

5.2. Топ-K наименьших
Задание:
Для списка nums и числа k реализуйте функцию
def k_smallest(nums: list[int], k: int) → list[int]:
которая возвращает K наименьших элементов за O(n + k log n), используя min-heap.
❓ Почему достаточно выполнить heapq.heapify один раз, а затем K раз heappop?

5.3. Слияние списков вручную
Задание:
Даны три отсортированных списка:
a, b, c.
Не используя heapq.merge, реализуйте функцию
def merge_three(a, b, c):
которая слияния их в один отсортированный список за O(n log 3).
❓ Почему при каждом шаге мы вытаскиваем минимум из трёх голов и помещаем следующий из того же списка?

5.4. Поток медиан
Задание:
Реализуйте класс
class MedianFinder:
с методами add_num(self, x) и find_median(self) → float,
используя две кучи (max-heap и min-heap).
❓ Зачем нужно балансировать размеры двух куч?

5.5. Алгоритм Дейкстры
Задание:
Дан ориентированный граф graph: dict[int, list[tuple[int,int]]],
где для каждой вершины список пар (сосед, вес).
Реализуйте функцию
def dijkstra(graph, start):
которая возвращает словарь кратчайших расстояний, используя min-heap для выбора ближайшей вершины.
❓ Почему при проверке d > dist[u] мы пропускаем устаревшие записи в куче?

5.1. Min-heap: каждый родитель ≤ своих детей; max-heap: каждый родитель ≥ своих детей.  
5.2. Потому что «всплытие» и «просеивание» проходят по высоте дерева ≈ log₂n.  
5.3. Узлы хранятся в массиве: для индекса i дети — 2i+1 и 2i+2, родитель — (i−1)//2.  
5.4. Храним отрицательные значения или кортеж (−priority, value).  
5.5. Для задач Top-K, потоковых медиан, Dijkstra — вместо полного сортирования O(n log n) можно получить O(n log k) или O(m log n).

import heapq
from typing import List, Dict, Tuple

# 5.1. Построение кучи
def build_heap(nums: List[int]) -> List[int]:
    heapq.heapify(nums)
    return nums

# 5.2. Топ-K наименьших
def k_smallest(nums: List[int], k: int) -> List[int]:
    if k <= 0: return [] heapq.heapify(nums) # O(n) return [heapq.heappop(nums) for _ in range(min(k, len(nums)))] # k * O(log n) # 5.3. Слияние трёх списков вручную def merge_three(a: List[int], b: List[int], c: List[int]) -> List[int]:
    heap: List[Tuple[int, int]] = []  # (value, source_index)
    res: List[int] = []
    arrays = [a, b, c]
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))  # значение, из какого списка, индекс в списке
    while heap:
        val, src, idx = heapq.heappop(heap)
        res.append(val)
        if idx + 1 < len(arrays[src]): heapq.heappush(heap, (arrays[src][idx+1], src, idx+1)) return res # 5.4. Поток медиан class MedianFinder: def __init__(self): self.lo: List[int] = [] # max-heap (отрицательные) self.hi: List[int] = [] # min-heap def add_num(self, x: int) -> None:
        if not self.lo or x <= -self.lo[0]: heapq.heappush(self.lo, -x) else: heapq.heappush(self.hi, x) # балансировка if len(self.lo) - len(self.hi) > 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) - len(self.lo) > 1:
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        if len(self.hi) > len(self.lo):
            return self.hi[0]
        return (-self.lo[0] + self.hi[0]) / 2

# 5.5. Алгоритм Дейкстры
def dijkstra(graph: Dict[int, List[Tuple[int,int]]], start: int) -> Dict[int, int]:
    dist: Dict[int, int] = {u: float('inf') for u in graph}
    dist[start] = 0
    heap: List[Tuple[int,int]] = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Деревья

Дерево — это набор узлов, где есть один корень, у каждого узла могут быть «дети», и все узлы связаны «рёбрами». Аналогия: семейное древо или организационная схема компании.

           [Корень]
           /      \
      [Узел1]    [Узел2]
       /   \        \
   [3]    [4]      [5]

• Родитель — узел выше (например, Корень для Узел1).
• Дети — узлы ниже (например, Узел1 → 3 и 4).
• Уровень — глубина от корня (корень = уровень 0).
• Высота — максимальный уровень в дереве.

Бинарное дерево

Каждый узел хранит не более двух детей: left и right.

• Доступ к детям — O(1).
• Поиск/вставка/удаление — O(n) в худшем случае (выстроилось в линию), O(log n) в среднем для сбалансированного.
• Память — O(n) для n узлов.

Пример реализации и основные операции

Обходы бинарного дерева

При обходе деревьев важен порядок посещения узлов:

• Preorder (корень → левое → правое):
  
  1. Обработка текущего узла
  2. Рекурсивный обход левого поддерева
  3. Рекурсивный обход правого поддерева
• Inorder (левое → корень → правое):
  
  1. Рекурсивный обход левого поддерева
  2. Обработка текущего узла
  3. Рекурсивный обход правого поддерева
• Postorder (левое → правое → корень):
  
  1. Рекурсивный обход левого поддерева
  2. Рекурсивный обход правого поддерева
  3. Обработка текущего узла

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# Поиск в дереве
def search(root, key):
    if not root or root.key == key:
        return root
    return search(root.left, key) if key < root.key else search(root.right, key)

# Вставка (обычное двоичное)
def insert(root, key):
    if not root:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

# Поиск минимума/максимума
def find_min(root):
    return root if not root.left else find_min(root.left)

def find_max(root):
    return root if not root.right else find_max(root.right)

# Удаление узла
def delete(root, key):
    if not root:
        return None
    if key < root.key: root.left = delete(root.left, key) elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # нет детей или один ребёнок
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # два ребёнка: заменить на следующий по величине
        succ = find_min(root.right)
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

# Обходы
def inorder(root):
    if root:
        yield from inorder(root.left)
        yield root.key
        yield from inorder(root.right)

def preorder(root):
    if root:
        yield root.key
        yield from preorder(root.left)
        yield from preorder(root.right)

def postorder(root):
    if root:
        yield from postorder(root.left)
        yield from postorder(root.right)
        yield root.key

Бинарное дерево поиска (BST)

В BST для каждого узла:

• Все ключи в левой ветви < ключа узла.
• В правой ветви > ключа узла.

Как происходит заполнение BST дерева

Скорость работы алгоритма бинарного поиска

Скорость заполнения и поиска в бинарном дереве O(log N). Скорость поиска в массиве — O(N). Ниже визуальное сравнение, почему так происходит.

Если вставлять уже упорядоченные данные (1,2,3,4…), BST вырождается в «список» (каждый узел имеет только правого ребёнка), поиск становится O(n). Случайный порядок или самобалансирующиеся деревья (AVL, Red-Black) избегают этого.

Самобалансирующиеся BST

• AVL-дерево: разница высот детей каждого узла ≤ 1. При вставке/удалении делает повороты (rotate) для восстановления баланса.
  
• Red-Black-дерево: каждый узел красный или чёрный, соблюдаются правила по путям от корня до листа. Менее жёстко балансируется, вставка/удаление быстрее (меньше поворотов).
  

# Пример одной итерации (LL-поворот) в AVL:
      [z]                   [y]
      /                     / \
    [y]         →         [x] [z]
    /
  [x]

Fenwick Tree (BIT)

Fenwick-дерево (или Дерево с бинарным индексом) — это удивительная структура данных, которая позволяет эффективно вычислять префикс-суммы и обновлять элементы. Как же это работает? Всё дело в уникальной организации хранения чисел. В корне дерева располагается сумма наибольшей возможной подпоследовательности четных элементов. На следующем уровне хранятся накопленные суммы четных половин — левой и правой. Далее идут четверти, и так далее. Листья дерева — это элементы массива, находящиеся на четных индексах.

Для лучшего понимания, представьте, что Fenwick-дерево помогает нам быстро справляться с задачами суммирования и обновления. Например, если мы хотим найти сумму первых нескольких четных элементов, дерево поможет сделать это без лишних усилий. С каждым уровнем мы как бы «сжимаем» информацию, что делает процесс поиска и обновления значительно быстрее.

Таким образом, Fenwick-дерево становится незаменимым инструментом для работы с числовыми последовательностями, позволяя не только легко находить нужные суммы, но и оперативно обновлять данные.

Заполнение дерева.

Это слайд-шоу требует JavaScript.

Поиск по дереву необходимой суммы

Это слайд-шоу требует JavaScript.

• update(i, delta): O(log n)
• prefix_sum(i): O(log n)

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.fw = [0]*(n+1)
    def update(self, i, delta):
        while i <= self.n: 
            self.fw[i] += delta 
            i += i & -i 
    def query(self, i): 
        s = 0 
        while i > 0:
            s += self.fw[i]
            i -= i & -i
        return s
# Использование:
# arr = [a1, a2, …]
# bit = Fenwick(len(arr))
# for i,val in enumerate(arr,1): bit.update(i,val)
# sum(arr[1..k]) = bit.query(k)

Segment Tree (дерево отрезков)

Поддерживает обобщённые запросы на любом отрезке и обновления в O(log n):

• Построение: O(n)
• Запрос на отрезке [l,r]: O(log n)
• Обновление одного элемента: O(log n)

Segment Tree простыми словами

Представь себе задачу: у тебя есть массив из n чисел, и ты хочешь очень быстро отвечать на вопросы «какая сумма (или минимум, максимум и т. д.) на отрезке [L…R]?», а также обновлять любое значение в массиве. Segment Tree (или «сегментное дерево») — это как дерево соревнований, где каждый узел хранит результат соревнования между двумя половинами своего отрезка.

• Как строится дерево:
  • В корне лежит агрегированный результат для всего массива [0…n−1].
  • Каждый узел на уровне ниже хранит результат для половины этого отрезка:
    • левый ребёнок → отрезок [L…mid]
    • правый ребёнок → отрезок [mid+1…R]
  • На листьях хранятся сами элементы массива (каждый лист = один элемент).
    

    Это слайд-шоу требует JavaScript.

    Это слайд-шоу требует JavaScript.
• Преимущества:
  • Запросы «сумма/минимум/максимум на отрезке [L…R]» выполняются за O(log n).
  • Обновление одного элемента (замена значения) тоже за O(log n).
  • Дерево статично по структуре (записали один раз) и затем просто ходим по нему.

Как выполняется запрос на отрезке [L…R]

1. Старшний узел (корень) — [0…n−1]. Если этот сегмент полностью внутри [L…R], сразу возвращаем его значение.
2. Если не полностью, проверяем левый и правый ребёнок:
   • Левый ребёнок покрывает [0…mid]. Если [0…mid] пересекается с [L…R], спускаемся в него.
   • Правый ребёнок покрывает [mid+1…n−1]. Если он пересекается с [L…R], спускаемся в него.
3. На каждом уровне мы «разбиваем» запрос на две части — по детям, но делаем это лишь по тем ветвям, которые пересекают [L…R]. Всего таких ветвей ≈ 2·log₂n.
4. Складываем (или берём минимум/максимум) результаты из тех узлов, которые полностью лежат внутри [L…R].
   

   Это слайд-шоу требует JavaScript.

   Это слайд-шоу требует JavaScript.

Как работает обновление элемента a[i] = x

1. Находим лист, соответствующий позиции i, и заменяем его значение на x.
2. Поднимаемся вверх по дереву: в каждом родительском узле пересчитываем агрегат из двух детей (сумма = left + right и т. д.).
3. Всего уровней ≈ log₂n, значит O(log n) шагов.

Это слайд-шоу требует JavaScript.

Это слайд-шоу требует JavaScript.

class SegmentTree:
    def __init__(self, arr):
        n = len(arr)
        self.size = 1
        while self.size < n: 
            self.size *= 2 
            self.tree = [0]*(2*self.size) 
        # заполнить листья 
        for i,v in enumerate(arr): 
            self.tree[self.size+i] = v 
        # построить внутренние узлы 
        for i in range(self.size-1, 0, -1): 
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1] 
    def update(self, pos, val): 
        i = pos + self.size 
        self.tree[i] = val 
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    def query(self, l, r):
        res = 0
        l += self.size; r += self.size
        while l <= r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if not r & 1:
                res += self.tree[r]
                r -= 1
            l //= 2; r //= 2
        return res
# Fenwick проще по коду, но только для префикс-сумм.
# Segment Tree универсальнее — любые отрезки, разные операции (мин, макс, gcd и т.д.).

Практические задачи с деревьями и индексными структурами

1. Проверка, является ли дерево BST
   Постановка: дан корень бинарного дерева. Нужно проверить, что для каждого узла все ключи в левом поддереве меньше, а в правом — больше его ключа.
   Алгоритм:
   1. Сделать inorder-обход и собрать ключи в список.
   2. Проверить, что полученный список отсортирован строго возрастающе.
2. Найти Lowest Common Ancestor (LCA) в BST
   Постановка: в BST найти наименьшего общего предка двух узлов с ключами p и q.
   Алгоритм:
   1. Начать с корня.
   2. Если оба ключа меньше корня → идти в левое поддерево.
   3. Если оба больше → идти в правое.
   4. Иначе текущий узел и есть LCA.
3. Префикс-суммы с Fenwick Tree
   Постановка: дан массив чисел, нужно быстро отвечать на запросы sum(1…i) и на обновления элементов arr[i] += Δ.
   Алгоритм:
   1. Построить Fenwick-дерево за O(n): вызвать update(i, arr[i]) для всех i.
   2. Для запроса sum(1…i) вызвать query(i).
   3. Для обновления arr[i] += Δ вызвать update(i, Δ).
4. Диапазонная сумма с Segment Tree
   Постановка: дан массив, нужно отвечать на запросы суммы на отрезках [l…r] и менять значение arr[i] = x.
   Алгоритм:
   1. Построить Segment Tree за O(n).
   2. Для запроса sum(l…r) выполнить query(l,r) за O(log n).
   3. Для обновления arr[i]=x выполнить update(i,x) за O(log n).
5. Подсчёт инверсий в массиве
   Постановка: дан массив чисел, нужно посчитать количество пар (i,j), где i<j и arr[i]>arr[j].
   Алгоритм:
   1. Сжать значения (coordinate compression) к диапазону 1…N.
   2. Идти слева направо, для каждого x добавлять в Fenwick:
      • inversions += i−1 − query(x) (число уже вставленных > x)
      • update(x, 1)

Решения

from collections import deque
import re

# 1. Проверка BST через inorder
def is_bst(root) -> bool:
    seq = list(inorder(root))
    return all(seq[i] < seq[i+1] for i in range(len(seq)-1))

# 2. LCA в BST
def lca_bst(root, p, q):
    node = root
    while node:
        if p < node.key and q < node.key: node = node.left elif p > node.key and q > node.key:
            node = node.right
        else:
            return node
    return None

# 3. Fenwick Tree
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.fw = [0]*(n+1)
    def update(self, i, delta):
        while i <= self.n: self.fw[i] += delta i += i & -i def query(self, i): s = 0 while i > 0:
            s += self.fw[i]
            i -= i & -i
        return s

# пример использования:
# arr = [a1, a2, a3, ...]
# bit = Fenwick(len(arr))
# for idx, v in enumerate(arr,1): bit.update(idx,v)
# bit.query(i), bit.update(i, Δ)

# 4. Segment Tree
class SegmentTree:
    def __init__(self, arr):
        n = len(arr)
        self.size = 1
        while self.size < n: self.size <<= 1 self.tree = [0]*(2*self.size) for i,v in enumerate(arr): self.tree[self.size+i] = v for i in range(self.size-1,0,-1): self.tree[i] = self.tree[2*i] + self.tree[2*i+1] def update(self, pos, val): i = pos + self.size self.tree[i] = val while i>1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    def query(self, l, r):
        res = 0
        l += self.size; r += self.size
        while l <= r:
            if l & 1:
                res += self.tree[l]; l += 1
            if not r & 1:
                res += self.tree[r]; r -= 1
            l//=2; r//=2
        return res

# 5. Подсчёт инверсий через Fenwick
def count_inversions(arr):
    # coordinate compression
    vals = sorted(set(arr))
    comp = {v:i+1 for i,v in enumerate(vals)}
    bit = Fenwick(len(vals))
    inv = 0
    for i, x in enumerate(arr,1):
        cx = comp[x]
        inv += (i-1) - bit.query(cx)
        bit.update(cx, 1)
    return inv

6.1. Что такое бинарное дерево поиска (BST) и какое основное свойство должно выполняться для каждого узла?

6.2. Почему при последовательной вставке отсортированных данных в обычный BST дерево вырождается в список? Как этого избежать?

6.3. Для каких задач удобнее использовать Fenwick Tree (BIT), а для каких — Segment Tree? В чём их ключевое различие?

6.4. Что такое Lowest Common Ancestor (LCA) в дереве, и как его можно найти в BST за O(h), где h — высота дерева?

6.5. Какие правила балансировки соблюдает AVL-дерево, а какие — Red-Black-дерево? Чем они отличаются по числу поворотов при вставке?

Задания. Блок 6. Деревья

Задание 6.1

Постановка задачи: В вашем приложении необходимо управлять динамическим набором цен товаров. Это включает в себя такие операции, как добавление, удаление и поиск цены, которая находится ближайше выше или ниже заданной (например, «цена ≥ X»).
Алгоритм:

1. Создайте бинарное дерево поиска (BST), где ключом будет цена товара.
2. Реализуйте операции вставки и удаления в соответствии со стандартными правилами работы с BST, что занимает O(h) времени.
3. При поиске цены «цена ≥ X» проходите по дереву: если узел.key < X, двигайтесь вправо; в противном случае запоминайте узел и продолжайте движение влево.

Дополнительное уточнение: Вместо простого описания, представим пример структуры данных. Используем словарь, где ключ — это название товара, а значение — его цена:

{
  "Товар A": 100,
  "Товар B": 150,
  "Товар C": 90
}

На выходе для операций:

Вставка: Добавление нового товара, например, «Товар D» с ценой 120. Словарь будет обновлен:

{
  "Товар A": 100,
  "Товар B": 150,
  "Товар C": 90,
  "Товар D": 120
}

Удаление: Удаление «Товар B». Словарь преобразится в:

{
  "Товар A": 100,
  "Товар C": 90,
  "Товар D": 120
}

Изменение цены: Изменение цены «Товар A» на 130. Обновленный словарь:

{
  "Товар A": 130,
  "Товар C": 90,
  "Товар D": 120
}

Поиск: Для запроса «цена ≥ 110» система вернет «Товар A» с ценой 130 и «Товар D» с ценой 120, так как они соответствуют критерию.

1. Реализовать BST, где ключ — цена.
2. Вставка и удаление по стандартным правилам BST O(h).
3. Для поиска «цена ≥ X» идти по дереву: если узел.key < X → вправо, иначе запомнить узел и идти влево.

6.2. Общий менеджер (LCA)
Постановка: в корпоративной иерархии задано дерево «менеджер→подчинённый». По двум сотрудникам найти их ближайшего общего руководителя — часто стоящая задача в больших организациях, где иерархия может быть довольно сложной. Это требуется для корректного решения вопросов взаимодействия или разрешения конфликтов.
Алгоритм:

1. Построить BST-подобную структуру для быстрого поиска по ID (или хранить parent-указатель). Это позволит эффективно организовать данные о сотрудниках и их руководителях, что значительно ускорит дальнейшие операции. Также можно использовать словарь, где ключом будет ФИО сотрудника, а значением — ФИО руководителя. Например:

employee_hierarchy = {
    "Иванов Иван Иванович": "Петров Пётр Петрович",
    "Сидорова Анна Сергеевна": "Петров Пётр Петрович",
    "Петрова Мария Васильевна": "Сидорова Анна Сергеевна",
    "Григорьев Алексей Николаевич": "Иванов Иван Иванович",
    "Олешко Настя Юрьевна": "Григорьев Алексей Николаевич"
}

2. Для каждого из двух узлов подняться к корню, сохраняя путь. Это шаг важен, так как он позволяет определить, какие узлы были посещены, и тем самым поможет в последующем сопоставлении. Мы можем хранить пути к корню для каждого из сотрудников в виде списков.
3. Пересечь два пути, найти первый общий узел — это LCA. Этот узел будет ближайшим общим начальником для предложенных сотрудников, и его можно использовать для дальнейшего анализа структуры команд.

6.3. Онлайн-аналитика посещений (Fenwick Tree)
Постановка: в веб-приложении фиксируются кол-ва посещений по часам. Нужно быстро отвечать на запрос «сколько визитов с начала дня до часа H» и при этом обновлять счётчик для текущего часа.

Скрипт генерации данных

import csv
import random
import datetime

def generate_fake_visits(date: datetime.date,
                         min_per_hour: int = 0,
                         max_per_hour: int = 100,
                         seed: int = 42) -> list[dict]:
    """
    Генерирует список посещений за указанный день.
    Для каждого часа [0..23] генерируется случайное число визитов
    в диапазоне [min_per_hour..max_per_hour], потом
    для каждого визита выбираются случайные минуты и секунды.
    """
    random.seed(seed)
    visits = []
    for hour in range(24):
        count = random.randint(min_per_hour, max_per_hour)
        for _ in range(count):
            minute = random.randint(0, 59)
            second = random.randint(0, 59)
            ts = datetime.datetime.combine(
                date,
                datetime.time(hour, minute, second)
            )
            visits.append({'timestamp': ts.isoformat()})
    # Перемешаем записи, чтобы порядок визитов был случайным
    random.shuffle(visits)
    return visits

def save_to_csv(visits: list[dict], filename: str = 'fake_visits.csv') -> None:
    """Сохраняет список словарей в CSV-файл с колонкой timestamp."""
    with open(filename, 'w', newline='', encoding='utf-8') as f:
        writer = csv.DictWriter(f, fieldnames=['timestamp'])
        writer.writeheader()
        writer.writerows(visits)
    print(f"Wrote {len(visits)} visits to '{filename}'")

if __name__ == '__main__':
    # Параметры генерации
    today = datetime.date.today()               # можно заменить на любую дату
    MIN_VISITS_PER_HOUR = 0                     # минимум визитов в час
    MAX_VISITS_PER_HOUR = 500                    # максимум визитов в час
    OUTPUT_CSV = 'fake_visits.csv'
    
    # Генерация и сохранение
    fake_visits = generate_fake_visits(
        date=today,
        min_per_hour=MIN_VISITS_PER_HOUR,
        max_per_hour=MAX_VISITS_PER_HOUR,
        seed=12345
    )
    save_to_csv(fake_visits, OUTPUT_CSV)

Алгоритм:

1. Создать Fenwick Tree размером 24 (для 24 часов).
2. При новом визите update(hour+1, 1).
3. Для запроса использовать query(H+1) — префикс-сумма.

6.4. Мониторинг пиковой нагрузки (Segment Tree)
Постановка: есть массив показателей нагрузки сервера по минутам за сутки (1440 точек). Нужно быстро находить максимальную и среднюю нагрузку на любом отрезке времени и обновлять отдельные значения.

Скрипт генерации данных

import csv
import random
import datetime

def generate_load_metrics(
    date: datetime.date,
    min_load: float = 0.0,
    max_load: float = 100.0,
    seed: int = 42,
    use_float: bool = True
) -> list[dict]:
    """
    Генерирует метрики нагрузки по минутам для одного дня.
    - date: дата, для которой создаются метрики;
    - min_load, max_load: диапазон нагрузок;
    - seed: для воспроизводимости;
    - use_float: если True — генерируются дробные значения (с двумя знаками после точки), иначе — целые.
    """
    random.seed(seed)
    metrics = []
    start_dt = datetime.datetime.combine(date, datetime.time(0, 0))
    for minute_offset in range(24 * 60):
        ts = start_dt + datetime.timedelta(minutes=minute_offset)
        raw = random.uniform(min_load, max_load) if use_float else random.randint(int(min_load), int(max_load))
        value = round(raw, 2) if use_float else raw
        metrics.append({
            'timestamp': ts.isoformat(sep=' '),
            'load': value
        })
    return metrics

def save_to_csv(metrics: list[dict], filename: str = 'load_metrics.csv') -> None:
    """Сохраняет список словарей в CSV-файл с колонками timestamp и load."""
    with open(filename, 'w', newline='', encoding='utf-8') as f:
        writer = csv.DictWriter(f, fieldnames=['timestamp', 'load'])
        writer.writeheader()
        writer.writerows(metrics)
    print(f"Wrote {len(metrics)} entries to '{filename}'")

if __name__ == '__main__':
    # Параметры генерации
    date = datetime.date.today()                   # или datetime.date(2025, 7, 27)
    MIN_LOAD = 10.0                                # минимальная нагрузка
    MAX_LOAD = 90.0                                # максимальная нагрузка
    USE_FLOAT = True                               # дробные значения?
    SEED = 12345                                   # для воспроизводимости
    OUTPUT_CSV = 'load_metrics.csv'
    
    # Генерация и сохранение
    metrics = generate_load_metrics(
        date=date,
        min_load=MIN_LOAD,
        max_load=MAX_LOAD,
        seed=SEED,
        use_float=USE_FLOAT
    )
    save_to_csv(metrics, OUTPUT_CSV)

Алгоритм:

1. Построить Segment Tree для суммы и максимума.
2. Для запроса «максимум/сумма» на отрезке [l…r] вызвать соответствующий query.
3. При изменении показателя update(pos, new_value).

6.5. Анализ аномалий в продажах (подсчёт инверсий)
Постановка: дана история ежедневных объёмов продаж за период. Нужно быстро определить, сколько раз продажи пошли вниз после предыдущего дня.

Скрипт генерации данных

import csv
import random
import datetime

def generate_monthly_sales(year: int,
                           month: int,
                           min_sales: int = 50,
                           max_sales: int = 50000,
                           seed: int = 42) -> list[dict]:
    """
    Генерирует данные продаж для указанного месяца.
    - year, month: год и месяц для генерации (1–12).
    - min_sales, max_sales: диапазон объёмов продаж.
    - seed: для воспроизводимости.
    Возвращает список словарей с ключами 'date' и 'sales'.
    """
    random.seed(seed)
    sales = []
    # Определяем количество дней в месяце
    first_day = datetime.date(year-5, month, 1)
    if month == 12:
        next_month = datetime.date(year + 1, 1, 1)
    else:
        next_month = datetime.date(year, month + 1, 1)
    num_days = (next_month - first_day).days

    for day_offset in range(num_days):
        current_date = first_day + datetime.timedelta(days=day_offset)
        qty = random.randint(min_sales, max_sales)
        sales.append({
            'date': current_date.isoformat(),
            'sales': qty
        })
    return sales

def save_to_csv(data: list[dict], filename: str = 'monthly_sales.csv') -> None:
    """
    Сохраняет список словарей в CSV-файл с колонками date и sales.
    """
    with open(filename, 'w', newline='', encoding='utf-8') as f:
        writer = csv.DictWriter(f, fieldnames=['date', 'sales'])
        writer.writeheader()
        writer.writerows(data)
    print(f"Wrote {len(data)} records to '{filename}'")

if __name__ == '__main__':
    # Параметры генерации
    YEAR = 2025
    MONTH = 7               # Июль, например
    MIN_SALES = 100         # Минимум продаж в день
    MAX_SALES = 1000        # Максимум продаж в день
    SEED = 20250727         # Для воспроизводимости
    OUTPUT_CSV = 'monthly_sales.csv'
    
    # Генерация и сохранение
    sales_data = generate_monthly_sales(
        year=YEAR,
        month=MONTH,
        min_sales=MIN_SALES,
        max_sales=MAX_SALES,
        seed=SEED
    )
    save_to_csv(sales_data, OUTPUT_CSV)

• i < j, то есть день i идёт раньше дня j
• и sales[i] > sales[j] — объём продаж в день i больше, чем в день j

Алгоритм:

1. Сжать значения продаж к 1…N.
2. Идти по дням в порядке времени, в Fenwick счётчике хранить сколько раз встретился каждый объём.
3. Для текущего x добавить к счёту (i−1) − query(cx), затем update(cx,1).

6.1. BST‐операции (insert/search/delete) работают за O(h), поиск «цена ≥ X» — O(h).  
6.2. LCA через поднятие по parent и пересечение путей — O(h).  
6.3. Fenwick: update и prefix_sum — O(log n), здесь n=24 → очень быстро.  
6.4. Segment Tree: построение O(n), запрос/обновление — O(log n).  
6.5. Подсчёт инверсий через Fenwick — O(n log n).

# 6.1. BST для цен
class Node:
    def __init__(self, key):
        self.key = key; self.left = self.right = None

def insert(root, key):
    if not root: return Node(key)
    if key < root.key: root.left = insert(root.left, key)
    else: root.right = insert(root.right, key)
    return root

def delete(root, key):
    if not root: return None
    if key < root.key: root.left = delete(root.left, key) elif key > root.key: root.right = delete(root.right, key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        succ = root.right
        while succ.left: succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

def find_next(root, x):
    res = None
    while root:
        if root.key >= x:
            res = root; root = root.left
        else:
            root = root.right
    return res.key if res else None

# 6.2. LCA в общем дереве с parent
def build_parent_map(edges):
    parent = {}
    for mgr, emp in edges:
        parent[emp] = mgr
    return parent

def lca(u, v, parent):
    def path(x):
        s = set()
        while x:
            s.add(x); x = parent.get(x)
        return s
    pu = path(u)
    while v not in pu:
        v = parent.get(v)
    return v

# 6.3. Fenwick для посещений
class Fenwick:
    def __init__(self, n):
        self.n = n; self.fw = [0]*(n+1)
    def update(self, i, d):
        while i<=self.n: self.fw[i]+=d; i+=i&-i def query(self, i): s=0 while i>0:
            s+=self.fw[i]; i-=i&-i
        return s

# 6.4. Segment Tree для нагрузки
class SegmentTree:
    def __init__(self, arr):
        n=len(arr); self.size=1
        while self.size1:
            i//=2
            self.tree_sum[i]=self.tree_sum[2*i]+self.tree_sum[2*i+1]
            self.tree_max[i]=max(self.tree_max[2*i],self.tree_max[2*i+1])
    def query_sum(self,l,r):
        res=0; l+=self.size; r+=self.size
        while l<=r:
            if l&1: res+=self.tree_sum[l]; l+=1
            if not r&1: res+=self.tree_sum[r]; r-=1
            l//=2; r//=2
        return res
    def query_max(self,l,r):
        res=0; l+=self.size; r+=self.size
        while l<=r:
            if l&1: res=max(res,self.tree_max[l]); l+=1
            if not r&1: res=max(res,self.tree_max[r]); r-=1
            l//=2; r//=2
        return res

# 6.5. Подсчёт инверсий в продажах
def count_inversions(arr):
    # сжатие
    vals=sorted(set(arr))
    comp={v:i+1 for i,v in enumerate(vals)}
    bit=Fenwick(len(vals))
    inv=0
    for i,x in enumerate(arr,1):
        cx=comp[x]
        inv += (i-1) - bit.query(cx)
        bit.update(cx,1)
    return inv

Дополнительная задача. Ограниченная максимальная подпоследовательность

Условие. Дан массив целых чисел a[0…n−1]. Нужно найти максимальную сумму его непрерывной подпоследовательности a[i…j], в которой число положительных чётных элементов кратно k=30. Ссылка на задание.

Сegментное дерево сдержит в каждом узле не одну, а k состояний: максимум среди подпоследовательностей внутри отрезка, сгруппированных по остатку от деления числа чётных положительных элементов на k.

Идея решения через Segment Tree

1. Структура узла. Для отрезка [L…R] в узле храним три массива длины k:
   • bestInside[r] — максимальная сумма непрерывной подпоследовательности полностью внутри [L…R] с количеством «хороших» элементов ≡ r (mod k);
   • bestPrefix[r] — максимальная сумма префикса [L…x] (L≤x≤R) с «хороших» ≡ r;
   • bestSuffix[r] — максимальная сумма суффикса [x…R] (L≤x≤R) с «хороших» ≡ r.
2. Инициализация листа. Для одного элемента a[p]:
   • Если a[p]>0 и чётно, то «хороших» = 1, иначе = 0.
   • Для всех r≠cnt ставим bestInside[r]=bestPrefix[r]=bestSuffix[r]=−∞,
   • для r=cnt эти три равны a[p].
3. Слияние двух детей L и R. Пусть у левого узла массивы L₁ и у правого R₁. Тогда в родительский узел:

   
   for r1 in range(k):
       for r2 in range(k):
           # 1) подпоследочка может лежать целиком в левом или в правом
           bestInside[(r1+r2)%k] = max(bestInside[(r1+r2)%k],
                                      L.bestSuffix[r1] + R.bestPrefix[r2])
   # копируем также внутрь лучшие из детей
   for r in range(k):
       bestInside[r] = max(bestInside[r], L.bestInside[r], R.bestInside[r])
   # префиксы: либо весь левый + префикс правого
   for r1 in range(k):
       for r2 in range(k):
           bestPrefix[(r1+r2)%k] = max(bestPrefix[(r1+r2)%k],
                                       L.bestPrefix[r1] + R.bestPrefix[r2])
   # либо просто префикс левого
   for r in range(k):
       bestPrefix[r] = max(bestPrefix[r], L.bestPrefix[r], R.bestPrefix[r])
   # аналогично для суффиксов
   for r1 in range(k):
       for r2 in range(k):
           bestSuffix[(r1+r2)%k] = max(bestSuffix[(r1+r2)%k],
                                       L.bestSuffix[r1] + R.bestSuffix[r2])
   for r in range(k):
       bestSuffix[r] = max(bestSuffix[r], L.bestSuffix[r], R.bestSuffix[r])
       

4. Ответ. После построения дерева в корне смотрим bestInside[0] — максимальную сумму с числом «хороших» ≡ 0 (т. е. кратно k).

Сложность

• Построение: O(n·k²) (слияние двух детей на каждом из O(n) узлов).
• Запрос за единичный отрезок (полный массив): O(1) (храним прямо в корне).
• Обновление элемента: O(log n·k²).

import sys
NEG_INF = -10**18

class SegTree:
    def __init__(self, a, k=30):
        self.n, self.k = len(a), k
        size = 1
        while size < self.n: size <<= 1 self.size = size # инициализируем пустыми узлами self.bestInside = [ [NEG_INF]*k for _ in range(2*size) ] self.bestPrefix = [ [NEG_INF]*k for _ in range(2*size) ] self.bestSuffix = [ [NEG_INF]*k for _ in range(2*size) ] for i,v in enumerate(a): cnt = 1 if (v>0 and v%2==0) else 0
            node = i + size
            for r in range(k):
                if r==cnt:
                    self.bestInside[node][r] = v
                    self.bestPrefix[node][r] = v
                    self.bestSuffix[node][r] = v
        # строим по уровням
        for node in range(size-1,0,-1):
            self._pull(node)

    def _pull(self, node):
        L, R, k = node*2, node*2+1, self.k
        BI, BP, BS = self.bestInside[node], self.bestPrefix[node], self.bestSuffix[node]
        LI, LP, LS = self.bestInside[L], self.bestPrefix[L], self.bestSuffix[L]
        RI, RP, RS = self.bestInside[R], self.bestPrefix[R], self.bestSuffix[R]
        # сброс
        for r in range(k):
            BI[r] = BP[r] = BS[r] = NEG_INF
        # bestInside
        for r in range(k):
            BI[r] = max(LI[r], RI[r])
        for r1 in range(k):
            if LS[r1]==NEG_INF: continue
            for r2 in range(k):
                if RP[r2]==NEG_INF: continue
                m = (r1+r2)%k
                BI[m] = max(BI[m], LS[r1] + RP[r2])
        # bestPrefix
        for r in range(k):
            BP[r] = LP[r]
        for r1 in range(k):
            if LP[r1]==NEG_INF: continue
            for r2 in range(k):
                if RP[r2]==NEG_INF: continue
                m = (r1+r2)%k
                BP[m] = max(BP[m], LP[r1] + RP[r2])
        # bestSuffix
        for r in range(k):
            BS[r] = RS[r]
        for r1 in range(k):
            if LS[r1]==NEG_INF: continue
            for r2 in range(k):
                if RS[r2]==NEG_INF: continue
                m = (r1+r2)%k
                BS[m] = max(BS[m], LS[r1] + RS[r2])

    def query_all(self):
        # корень хранит ответ по всему массиву
        return self.bestInside[1][0]

# Пример использования:
if __name__ == "__main__":
    a = [ 5, -1, 4, 2, 6, -3, 8, 10, -2, 1 ]
    st = SegTree(a, k=30)
    print("Максимальная сумма с кол-вом чётных>0 ≡0 mod 30:", st.query_all())

7. Графы

Граф — это набор «точек» (вершин) и «линий» (рёбер), которые между ними соединяют.

Представь, что вершины — это города, а рёбра — дороги между ними. В олимпиадах графы — основа для задач про маршруты, связи и оптимизацию путей.

7.1 Представления графа

Существует несколько способов хранить граф в памяти. Выбираем тот, что быстрее и экономичнее для вашей задачи.

Список смежности

• Для каждой вершины хранится список соседей: adj[u] = [v1, v2, …].
• Очень удобно для разреженных графов (мало рёбер).
• Операция «обход всех соседей u» — O(deg(u)).

from collections import defaultdict

adj = defaultdict(list)
# добавляем неориентированное ребро u–v:
def add_edge(u, v):
    adj[u].append(v)
    adj[v].append(u)

Когда выгодно: если число рёбер E ≪ V², экономим память O(V + E).

Матрица смежности

• Двумерный массив mat[u][v] = 1 если есть ребро, иначе 0.
• Быстрый доступ «есть ли ребро u→v?» — O(1).
• Занимает O(V²) памяти.

# инициализация для V вершин:
V = 5
mat = [[0]*V for _ in range(V)]
def add_edge(u, v):
    mat[u][v] = 1
    mat[v][u] = 1  # для неориентированного графа

Когда выгодно: мелкие графы или плотные (E≈V²), часто в задачах с быстрым «существует ли путь».

Список рёбер

• Просто коллекция пар (u, v) или тройек (u, v, w) для взвешенных.
• Нужен, если алгоритм сначала сортирует рёбра (Крускал, DSU).

edges = []
# добавить ребро u–v (взвешенное):
def add_edge(u, v, w):
    edges.append((w, u, v))  # сортировка по весу

7.2 Взвешенные и ориентированные графы

• Ориентированный граф (digraph): ребро имеет направление u→v. Храним отдельно в adj_out[u] и, при необходимости, adj_in[v].
• Взвешенный граф: каждому ребру сопоставлен вес w (стоимость, длина дороги). В списке смежности храним пары (v, w).

# пример списка смежности для взвешенного ориентированного графа:
adj = defaultdict(list)
def add_edge(u, v, w):
    adj[u].append((v, w))  # из u в v с весом w

Выбор контейнера: если много вставок/удалений — defaultdict(list), если нужен быстрый поиск по весу — можно использовать heapq внутри обхода.

7.3 Практические примеры

Простой: DFS рекурсией

Обход в глубину (DFS) — «путешествие по лабиринту»: идём по одному пути, пока не упремся, потом возвращаемся назад и ищем другой.

visited = set()
def dfs(u):
    if u in visited:
        return
    visited.add(u)
    # здесь "обрабатываем" вершину u
    for v in adj[u]:
        dfs(v)

# Запуск:
dfs(start_vertex)

Средний: BFS — кратчайший путь в невзвешенном графе

Обход в ширину (BFS) — находим все вершины на расстоянии 1, потом на 2 и т.д. В невзвешенном графе это гарантированный кратчайший путь по числу рёбер.

from collections import deque

def bfs(start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist  # расстояния от start

Сложный: Крускал + DSU (минимальное остовное дерево)

Найти набор рёбер, который соединит все вершины с минимальной суммарной длиной дорог. Мы сортируем рёбра по весу и подключаем, если они не создают цикл (система непересекающихся множеств — DSU).

# DSU (Disjoint Set Union)
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        self.p[rb] = ra
        return True

def kruskal(n, edges):
    """n — число вершин, edges — список (w,u,v)"""
    dsu = DSU(n)
    mst_weight = 0
    edges.sort()
    for w, u, v in edges:
        if dsu.union(u, v):
            mst_weight += w
    return mst_weight

# Пример
n = 5
edges = [(1,0,1),(3,0,2),(2,1,2),(4,2,3),(5,3,4)]
print("MST weight:", kruskal(n, edges))  # 1+2+4+5=12

❓ Вопросы для самопроверки:
– Какие операции DFS/BFS выполняются за O(V+E)?
– Почему Kruskal использует сортировку рёбер — O(E log E)?
– Как переделать BFS, чтобы он возвращал не только дистанции, но и сами пути?

Задания. Блок 7. Графы

Задание 7.1.
Простой: напишите функцию dfs(graph: dict[int,list[int]], start: int) → List[int], которая рекурсивно обходит все достижимые из start вершины в неориентированном графе, заданном списком смежности, и возвращает порядок посещения.

Задание 7.2.
Средний: напишите функцию bfs_shortest_path(graph: dict[int,list[int]], src: int, dst: int) → int, которая возвращает длину кратчайшего пути (число рёбер) между src и dst в неориентированном невзвешенном графе или -1, если пути нет.

Задание 7.3.
Сложный: реализуйте алгоритм Крускала для MST. Функция kruskal(n: int, edges: List[Tuple[int,int,int]]) → int получает число вершин и список рёбер (u,v,weight) и возвращает суммарный вес минимального остовного дерева.

Задание 7.4.
В задаче управления зависимостями пакетов заданы пакеты и их зависимости в виде ориентированных рёбер (pkg, dep), означающих «pkg зависит от dep». Напишите функцию has_cycle(deps: List[Tuple[str,str]]) → bool, которая возвращает True, если в графе есть цикл зависимостей, иначе False. Это позволит обнаружить «циркулярные» зависимости.

Задание 7.5.
В навигационной системе задан взвешенный ориентированный граф дорог в виде списка смежности: graph: Dict[int, List[Tuple[int,int]]], где каждая пара (to, cost). Напишите функцию dijkstra(graph, src: int) → Dict[int,int], которая возвращает словарь минимальных расстояний от src до всех достижимых вершин.

7.4.  
True, если обнаружен цикл; например для [("A","B"),("B","C"),("C","A")] → True, иначе False.

7.5.  
Для графа 
{
 1: [(2,5),(3,2)],
 2: [(4,1)],
 3: [(2,1),(4,7)],
 4: []
}
dijkstra(..., src=1) возвращает {1:0, 3:2, 2:3, 4:4}.

# 7.4. Поиск цикла в ориентированном графе через DFS + трёхцветная метка
from collections import defaultdict

def has_cycle(deps):
    graph = defaultdict(list)
    for pkg, dep in deps:
        graph[pkg].append(dep)
    color = {}  # 0=белый, 1=серый, 2=чёрный

    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if color.get(v,0) == 1:
                return True
            if color.get(v,0) == 0 and dfs(v):
                return True
        color[u] = 2
        return False

    for node in graph:
        if color.get(node,0) == 0 and dfs(node):
            return True
    return False

# Пример:
print(has_cycle([("A","B"),("B","C"),("C","A")]))  # True
print(has_cycle([("A","B"),("B","C"),("D","A")]))  # False


# 7.5. Алгоритм Дейкстры с heapq
import heapq

def dijkstra(graph, src):
    dist = {src: 0}
    hq = [(0, src)]
    while hq:
        d, u = heapq.heappop(hq)
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(hq, (nd, v))
    return dist

# Пример:
graph = {
    1: [(2,5),(3,2)],
    2: [(4,1)],
    3: [(2,1),(4,7)],
    4: []
}
print(dijkstra(graph, 1))
# {1: 0, 3: 2, 2: 3, 4: 4}

Специализированные структуры для олимпиад

Иногда стандартных списков и словарей недостаточно: нужны структуры, которые умеют быстро «склеивать» множества, хранить случайно сбалансированные деревья или компактно представлять наборы до 64 элементов. Такие структуры часто встречаются в задачах на DSU, динамические строки и компактные бит-множества.

► DSU / Union-Find

Зачем нужен: когда нужно объединять группы (города, компоненты графа) и быстро проверять, в одной ли они «команде». DSU (англ. Disjoint Set Union) хранит для каждого элемента ссылку на «начальника» (parent) и «высоту» дерева (rank), а при каждом запросе «найти группу» сжимает путь, чтобы следующий поиск был ещё быстрее.

Аналогия: представь дуб, где листья — это элементы, а ветки ведут к стволу. Path-compression — это когда после поиска всех листьев сразу подгибают к стволу, чтобы в следующий раз добраться до ствола одним прыжком.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # находим «начальника» и сжимаем путь
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        # прикрепляем «короткое дерево» к «высокому»
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

► Декартово дерево (treap)

Что это: похоже на самобалансирующееся двоичное дерево поиска, но баланс обеспечивается случайными «приоритетами». Каждый узел хранит key и случайное priority. При вставке дерево «просеивается» как куча по priority, сохраняя свойства BST по key.

Зачем: умеет split (разделить по ключу) и merge (склеить два дерева) за O(log n) в среднем. В олимпиадах удобно для динамических строк (“rope”), когда надо быстро вырезать и вставлять подстроки.

import random

class TreapNode:
    __slots__ = ('key','prio','left','right')
    def __init__(self, key):
        self.key = key
        self.prio = random.random()
        self.left = self.right = None

def split(root, key):
    if not root:
        return (None, None)
    if key < root.key: left, root.left = split(root.left, key) return (left, root) else: root.right, right = split(root.right, key) return (root, right) def merge(left, right): if not left or not right: return left or right if left.prio > right.prio:
        left.right = merge(left.right, right)
        return left
    else:
        right.left = merge(left, right.left)
        return right

def insert(root, node):
    if not root:
        return node
    if node.prio > root.prio:
        node.left, node.right = split(root, node.key)
        return node
    elif node.key < root.key:
        root.left = insert(root.left, node)
    else:
        root.right = insert(root.right, node)
    return root

► Битовые множества

Когда у вас многократные проверки вхождения для небольшого диапазона (≤ 64), можно хранить набор в одном 64-битном числе. Операции «добавить», «удалить», «проверить» — всё за O(1) через битовые маски.

# множество чисел 0..63 в битовой форме
mask = 0
def add(mask, x):      # добавить x
    return mask | (1 << x)
def remove(mask, x):   # удалить x
    return mask & ~(1 << x) def contains(mask, x): # есть ли x? return (mask >> x) & 1 == 1

# пример: множество {1,3,5}
mask = add(mask, 1)
mask = add(mask, 3)
mask = add(mask, 5)
print(contains(mask,3))  # True
print(bin(mask))         # 0b101010

Для динамического расширения до больших N используют bitarray или array('L'), но идея та же — упаковать биты в слова.

Примеры задач

Простой: DSU — соединить города

# есть N городов и M дорог, нужно узнать число компонент
dsu = DSU(N)
for u, v in roads:
    dsu.union(u, v)
# считаем, сколько разных «начальников»
components = len({dsu.find(i) for i in range(N)})

Средний: treap-rope для перестановки подстроки

Храним строку как treap, в котором in-order обход даёт исходный текст. Чтобы вырезать и вставить фрагмент:

1. split по началу и концу фрагмента → три дерева (A, B, C).
2. merge(A, C) убирает B из текста.
3. split итогового по месту вставки и merge(A, B, C) ставит фрагмент в новое место.

Сложный: Bloom-фильтр

Probabilistic структура, которая хранит «множество» и может ложно сказать «да» (коллизия), но никогда не скажет «нет» для добавленных элементов. Реализуется как большой бит-массив + несколько хешей. Проверка и вставка — O(k), где k — число хешей.

class BloomFilter:
    def __init__(self, size, hashes):
        self.size = size
        self.bitset = 0
        self.hashes = hashes  # список функций hash(x)→int

    def add(self, x):
        for h in self.hashes:
            self.bitset |= 1 << (h(x) % self.size) def contains(self, x): return all((self.bitset >> (h(x) % self.size)) & 1
                   for h in self.hashes)

❓ Контрольные вопросы:
– Почему DSU.find «сжимает путь» и как это ускоряет операции?
– В treap при каком условии новый узел становится корнем?
– Какие ограничения есть у битовых множеств на 64 элемента?
– Откуда в Bloom-фильтре возникает ложное срабатывание? Как снизить вероятность коллизий?

Задания. Блок 8. Специализированные структуры для олимпиад

Задание 8.1.
Простой: дано n городов и список дорог roads: List[Tuple[int,int]] между ними. С помощью DSU (Union-Find) реализуйте функцию count_components(n, roads) → int, которая возвращает число связных компонент.

Задание 8.2.
Средний: реализуйте «rope» на основе декартова дерева (treap) с операциями split и merge над строкой. Напишите функции insert(root, pos, substr) и delete(root, l, r) для вставки подстроки и удаления от l до r.

Задание 8.3.
Сложный: реализуйте Bloom-фильтр на битовом массиве длины m с k хеш-функциями h₁…hₖ. Должны быть методы add(x) и contains(x) → bool (с ложноположительными срабатываниями не чаще, чем (1–e<sup>–kn/m</sup>)ᵏ).

Задание 8.4.
Практика битовых масок: шахматная доска 8×8 кодируется 64-битным целым, где бит r*8 + c соответствует клетке с координатами (r,c) (от 0 до 7). Напишите функцию rook_moves(pos: int) → int, возвращающую битовую маску всех клеток, на которые может ходить ладья с позиции pos, если доска пуста (все клетки доступны). Используйте побитовые сдвиги и маскирование.

Задание 8.5.
Практика битовых массивов: реализуйте решето Эратосфена для поиска простых до N, используя bytearray или bitarray (по одному биту на чёт/нечёт). Функция sieve(N) → List[int] должна работать быстро при N≤10⁷.

8.1. Компонентов =  n – (число успешных «union»). Например для n=5 и roads=[(0,1),(1,2),(3,4)] → 2.

8.2. Нетривиально приводить здесь код, но базовые операции split/merge за O(log n).

8.3. Bloom-фильтр правильно выставляет биты и проверяет их; тестами можно подтвердить теоретическую вероятность.

8.4. Для ладьи из центра (r=3,c=3 → pos=1<<(3*8+3)=1<<27) функция вернёт mask = 
0x0000000810204080 | 0x0080808080808080 = 0x0080808818_204080

8.5. При N=30 ← [2,3,5,7,11,13,17,19,23,29].

# 8.1. DSU
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self, x):
        while self.p[x]!=x:
            self.p[x]=self.p[self.p[x]]
            x=self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra==rb: return False
        if self.r[ra]<self.r[rb]: ra, rb = rb, ra self.p[rb]=ra if self.r[ra]==self.r[rb]: self.r[ra]+=1 return True def count_components(n, roads): dsu = DSU(n) cnt = n for u,v in roads: if dsu.union(u,v): cnt -= 1 return cnt # 8.2. Treap-rope (схема) import random class Node: __slots__ = ('val','prio','size','left','right') def __init__(self, val): self.val = val self.prio = random.random() self.size = 1 self.left = self.right = None def upd(n): n.size = 1 + (n.left.size if n.left else 0) + (n.right.size if n.right else 0) def split(root, k): if not root: return (None,None) if (root.left.size if root.left else 0) >= k:
        l,r = split(root.left, k)
        root.left = r; upd(root)
        return (l, root)
    else:
        l,r = split(root.right, k - (1 + (root.left.size if root.left else 0)))
        root.right = l; upd(root)
        return (root, r)

def merge(a, b):
    if not a or not b: return a or b
    if a.prio < b.prio:
        a.right = merge(a.right, b); upd(a); return a
    else:
        b.left = merge(a, b.left); upd(b); return b

# insert(root,pos,substr) и delete(root,l,r) строятся через split/merge

# 8.3. Bloom-фильтр
class Bloom:
    def __init__(self, m, k, hashes):
        self.m, self.k = m, k
        self.array = 0
        self.hashes = hashes
    def add(self, x):
        for h in self.hashes:
            self.array |= 1 << (h(x) % self.m) def contains(self, x): return all((self.array >> (h(x)%self.m)) & 1 for h in self.hashes)

# 8.4. Ходы ладьи bitboard
def rook_moves(pos):
    r = pos >> 3  # row index 0–7
    c = pos & 7   # col index
    row_mask = 0xFF << (r*8)
    col_mask = sum(1<<(c + 8*i) for i in range(8))
    # исключаем исходную клетку, но можно оставить
    return (row_mask | col_mask) ^ (1 << (r*8 + c))

# Пример:
center = 3*8 + 3
print(hex(rook_moves(center)))
# 0x0080808818204080  (биты по файлам и рангу)

# 8.5. Решето Эратосфена на bytearray
def sieve(N):
    is_prime = bytearray(b'\x01')*(N+1)
    is_prime[0]=is_prime[1]=0
    for i in range(2, int(N**0.5)+1):
        if is_prime[i]:
            step = i
            start = i*i
            is_prime[start:N+1:step] = b'\x00'*(((N - start)//step)+1)
    return [i for i,pr in enumerate(is_prime) if pr]

# Пример:
print(sieve(30))
# [2,3,5,7,11,13,17,19,23,29]

9. Выбор структуры и оценка сложности

Когда перед вами стоит задача выбрать, где и как хранить данные, важно понимать не только что делают структуры, но и сколько это будет стоить по времени и памяти. Ниже — четыре шага, которые помогут сделать обоснованный выбор.

► Таблица «Операции ↔ O-сложность»

Зачем: на олимпиадах часто нужно быстро оценить, выдержит ли структура миллион вставок или сотни тысяч запросов на поиск.

Шаги:

1. Соберите список операций, которые вам важны: вставка, удаление, поиск по ключу, получение минимума/максимума.
2. Сравните доступные структуры по их теоретическим сложностям.

► Память в CPython

Зачем: иногда батарейки не хватает из-за чрезмерных накладных расходов на объекты.

Шаги:

1. Посмотрите, сколько «весит» один элемент: sys.getsizeof(obj).
2. Сравните хранение примитивов (список) и упакованных массивов (array('I') или bytes).
3. Узнайте про __slots__ — убирает словарь экземпляра и экономит ~50 % памяти на объект.

import sys
from array import array

# список из миллиона чисел
lst = list(range(10**6))
arr = array('I', range(10**6))

print("list:", sys.getsizeof(lst), "bytes")
print("array:", sys.getsizeof(arr), "bytes")  # экономия ~half

■ Кейс: миллион записей «id→счётчик»

Условие: нужно обновлять счётчик по id и быстро читать его значение.

Варианты:

1. list или array по индексу
   • Требует плотно упакованный диапазон 0…N−1.
   • Обновление и чтение — O(1), память — N×4 байта (array(‘I’)).
   • Проблема: id не всегда подряд, иногда разбросаны.
2. dict
   • Поддерживает любые id (не подряд).
   • Обновление и чтение — O(1) амортизированно.
   • Накладные расходы на хэш-таблицу: ~50–100 байт на запись.

Вывод: если id — плотный диапазон 0…N−1 → array. Иначе → dict.

♦ Вопрос-ответ

❓ Какая структура даёт одновременно O(1) поиск и упорядоченное хранение?
— Никакая «из коробки». Для этого берут две: dict (поиск) + deque или list (порядок), или используют спецбиблиотеки (sortedcontainers), где поиск O(log n).

❓ Почему в Python поиск в dict считается амортизированно O(1), а не строго O(1)?
— Потому что при редких «резких» расширениях хэш-таблицы (resize) одна операция может занять O(n), но это происходит редко, и среднее время остаётся O(1).

11. Шаблоны олимпиадных задач

На олимпиадах часто встречаются похожие приёмы решения — их называют шаблонами. Зная эти 7 «хитрых ходов», ты сможешь быстро подобрать нужную структуру и алгоритм.

11.1 Каталог 7 шаблонов

• Sliding-window — скользящее окно по массиву для поиска подотрезка с нужным свойством.
• Two-sum — найти две суммы (пару элементов), дающие заданное значение.
• DSU-дорожки (Union-Find) — объединение и поиск по компонентам связности.
• Range-sum — обработка запросов «сумма на отрезке» (Fenwick / префиксные суммы).
• Heap-K-top — поддержка K-го по величине элемента (min-heap или max-heap).
• BFS-0-1 — поиск кратчайшего пути на графе с рёбрами весов 0 или 1.
• LRU-cache — реализация кэша «последнего наиболее редкого» через dict + двусвязный список.

11.2 Пятиминутные примеры (≤25 строк)

def max_sum_subarray(nums, k):
    # найти максимум суммы в окне длины k
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i-k]  # добавили справа, убрали слева
        best = max(best, window_sum)
    return best

# Пример:
# nums = [1,2,3,4,5], k=3 → окна [1,2,3]=6, [2,3,4]=9, [3,4,5]=12 → ответ 12

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None

# Пример:
# nums=[2,7,11,15], target=9 → (0,1) потому что nums[0]+nums[1]=9

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1

# Пример:
# dsu = DSU(5); dsu.union(0,1); dsu.union(1,2); группы: {0,1,2}, {3}, {4}

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

    def update(self, i, delta):
        while i <= self.n: self.fw[i] += delta i += i & -i def query(self, i): s = 0 while i > 0:
            s += self.fw[i]
            i -= i & -i
        return s

# Пример:
# A = [0,1,2,3,4], fenw = Fenwick(5)
# for i,x in enumerate(A,1): fenw.update(i,x)
# sum A[1..3] = fenw.query(3) = 1+2+3 = 6

import heapq

def k_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)        # O(k)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap  # в куче остаются k наибольших

# Пример:
# nums=[5,1,3,6,8,2], k=3 → heap=[6,8,5] (неотсортированно)

from collections import deque

def bfs01(n, adj):
    INF = 10**18
    dist = [INF]*n
    dq = deque([0])
    dist[0] = 0
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

# Пример:
# adj = {0: [(1,0),(2,1)], 1:[(2,0)], 2:[]}
# bfs01(3, adj) → [0,0,0]

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.d = {}
        self.head = Node(0,0); self.tail = Node(0,0)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        p, n = node.prev, node.next
        p.next, n.prev = n, p

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.d: return -1
        node = self.d[key]
        self._remove(node); self._add_front(node)
        return node.val

    def put(self, key, val):
        if key in self.d:
            self._remove(self.d[key])
        node = Node(key,val)
        self._add_front(node)
        self.d[key] = node
        if len(self.d) > self.cap:
            tail = self.tail.prev
            self._remove(tail)
            del self.d[tail.key]

class Node:
    def __init__(self,k,v):
        self.key, self.val = k, v
        self.prev = self.next = None

11.3 ❓ Выберите подходящий шаблон

1. Найти в массиве подотрезок длины ≤ K с максимальной суммой. → Sliding-window
2. Дано N пар чисел, нужно быстро объединять по равенству первого и суммировать вторые. → DSU-дорожки
3. Есть поток на миллион обновлений “прибавить x к индексу i” и миллион запросов суммы от начала до i. → Range-sum (Fenwick)
4. Нужно отвечать на запрос “какие 10 самых больших значений мы видели за всё время?”. → Heap-K-top
5. Граф, рёбра 0/1, найти кратчайший путь от 1 до N. → BFS-0-1

Практикум

Практикум. Блок A. Последовательности «из коробки»

Задание A1. «Rotate Array».
Напишите две функции, которые поворачивают список arr длины n вправо на k позиций:

1. Используя обычный list, за O(n).
2. Используя collections.deque и метод rotate.

Сравните время выполнения на случайном массиве из 10 000 000 элементов для k=1234.

Задание A2. «Sliding Window Sum».
Дан список целых arr длины n и окно w. Нужно вычислить сумму каждого подмассива длины w:

1. Реализуйте на list за O(n·w).
2. Реализуйте с помощью deque и скользящего обновления суммы за O(n).

Проверьте на n=1e6, w=1000.

Задание A3. «Matrix 3×3 Convolution».
Дана матрица m×m (например, m=500) и ядро 3×3. Вычислите результат свёртки на «скользящем окне» 3×3 по всей матрице:

1. Через вложенные for-циклы и обычные списки.
2. Через срезы и zip для ускорения.

Сравните время на случайной матрице.

Задание A4. «Top K Frequent».
Дан большой список слов (n=5e6, случайные строки длины 5–10). Нужно найти k самых частых слов:

1. С помощью collections.Counter и most_common.
2. С помощью heapq.nlargest на словаре частот.

Сравните по памяти и скорости для k=100.

Задание A5. «Merge Intervals».
Дан список несортированных интервалов [(lᵢ,rᵢ)]. Объедините все пересекающиеся интервалы и верните результат отсортированным. Реализуйте:

1. Через list.sort + однопроходное слияние.
2. Через deque для хранения текущего «стека» интервалов.

Проверьте на 1 000 000 случайных интервалов.

A1. list: ~0.12 s; deque.rotate: ~0.02 s.
A2. list: ~12 s; deque: ~0.05 s.
A3. naive: ~3.5 s; zip-slices: ~1.1 s.
A4. Counter.most_common: ~0.8 s, uses ~200 MB; heapq.nlargest: ~1.2 s, ~150 MB.
A5. Оба за O(n log n): list+sort ~0.4 s; deque variant ~0.5 s.

import time, random
from collections import deque, Counter
import heapq

# A1
def rotate_list(arr, k):
    k %= len(arr)
    return arr[-k:] + arr[:-k]

def rotate_deque(arr, k):
    dq = deque(arr)
    dq.rotate(k)
    return list(dq)

# A2
def sliding_list(arr, w):
    n = len(arr)
    return [sum(arr[i:i+w]) for i in range(n-w+1)]

def sliding_deque(arr, w):
    dq = deque(arr[:w])
    s = sum(dq)
    res = [s]
    for x in arr[w:]:
        s += x - dq.popleft()
        dq.append(x)
        res.append(s)
    return res

# A3
def conv_naive(mat):
    m = len(mat)
    res = [[0]*(m-2) for _ in range(m-2)]
    for i in range(m-2):
        for j in range(m-2):
            s = 0
            for di in range(3):
                for dj in range(3):
                    s += mat[i+di][j+dj]
            res[i][j] = s
    return res

def conv_zip(mat):
    m = len(mat)
    res = []
    for i in range(m-2):
        rows = mat[i:i+3]
        row_iter = list(zip(*rows))
        res.append([ sum(col[j:j+3]) for j in range(m-2) for col in [row_iter] ][::(m-2)])
    return [row[i*(m-2):(i+1)*(m-2)] for i,row in enumerate(res)]

# A4
def top_k_counter(words, k):
    return Counter(words).most_common(k)

def top_k_heap(words, k):
    freq = Counter(words)
    return heapq.nlargest(k, freq.items(), key=lambda x: x[1])

# A5
def merge_intervals_sort(intv):
    intv.sort()
    res = []
    for l,r in intv:
        if not res or res[-1][1] < l:
            res.append([l,r])
        else:
            res[-1][1] = max(res[-1][1], r)
    return res

def merge_intervals_deque(intv):
    from collections import deque
    intv.sort()
    dq = deque()
    for l,r in intv:
        if not dq or dq[-1][1] < l:
            dq.append([l,r])
        else:
            dq[-1][1] = max(dq[-1][1], r)
    return list(dq)

Пример вывода (первые 5 сумм):
12345
13012
…

# Fenwick
class Fenwick:
    def __init__(self, a):
        self.n = len(a)
        self.fw = [0]*(self.n+1)
        for i,v in enumerate(a,1):
            self._add(i,v)
    def _add(self,i,v):
        while i<=self.n: self.fw[i]+=v i+=i&-i def update(self,i,x): # a[i] = x curr = self.query(i,i) self._add(i, x-curr) def prefix(self,i): s=0 while i>0:
            s+=self.fw[i]
            i-=i&-i
        return s
    def query(self,l,r):
        return self.prefix(r)-self.prefix(l-1)

# Чтение и обработка
with open('data.txt') as f:
    arr = [int(line) for line in f]
fw = Fenwick(arr)
out = []
with open('queries.txt') as f:
    for line in f:
        cmd,*rest = line.split()
        if cmd=='sum':
            l,r = map(int,rest)
            out.append(str(fw.query(l,r)))
        else:
            i,x = map(int,rest)
            fw.update(i, x)
print('\n'.join(out))

0  5  12  …  INF

import heapq
def dijkstra_heapq(n, adj, src=1):
    dist = [float('inf')]*(n+1)
    dist[src]=0
    pq = [(0,src)]
    while pq:
        d,u = heapq.heappop(pq)
        if d>dist[u]: continue
        for v,w in adj[u]:
            if dist[v]>d+w:
                dist[v]=d+w
                heapq.heappush(pq,(dist[v],v))
    return dist

# Своя куча (упрощённо)
class MinHeap:
    def __init__(self): self.a=[]
    def push(self,x): self.a.append(x); self._sift_up(len(self.a)-1)
    def pop(self):
        val = self.a[0]
        self.a[0]=self.a[-1]; self.a.pop()
        self._sift_down(0)
        return val
    # ... реализация sift_up/sift_down аналогично heapq …

# C1 можно запустить оба варианта и замерить.

Практикум. Итоговая проверка (12 тестовых вопросов)

1. 1. Какой метод у list — O(1): append или insert(0,x)? (выберите один)
   2. Что возвращает deque.rotate(3)?
   3. Сколько бит нужно, чтобы закодировать слово длины 5 из алфавита размера 26?
   4. Какова сложность Counter.most_common(k)?
   5. Что такое «lazy propagation» в сегментном дереве?
   6. Какой оператор Python инвертирует побиты в 32-битном числе?
   7. Что делает heapq.merge?
   8. Как фирма проверяет, что слову принадлежит один код в префикс-коде (условие Фано)?
   9. Как обновить значение в Fenwick-дереве?
   10. Почему Dijkstra не работает с отрицательными весами?
   11. Как получить популяцию бит (число единиц) в Python?
   12. Что быстрее для FIFO: list.pop(0) или deque.popleft()?