Алгоритмы и структуры данных на C/C++: шпаргалка к экзамену (МИФИ, МГУ, МФТИ)

Алгоритмы — это пошаговые рецепты решения задач. Представьте кулинарный рецепт: «возьмите яйца, разбейте, смешайте, жарьте 5 минут» — каждый шаг строго определён, и порядок шагов имеет значение (нельзя сначала пожарить, а потом разбить яйца). Точно так же алгоритм — это конечная последовательность однозначных инструкций, которая преобразует входные данные в выходные за гарантированное число шагов. Главные свойства хорошего алгоритма: детерминированность (при одних и тех же входных данных всегда получается один и тот же результат) и конечность (он обязан завершиться, а не зациклиться навсегда). Без этих двух свойств «алгоритм» превращается в «эвристику» или в бесконечный цикл.

Структуры данных — это способы хранить информацию так, чтобы с ней было удобно работать. Аналогия — полки, ящики и папки в офисе: документы лежат не в одной куче, а разложены по темам, отделам и алфавиту, чтобы их можно было быстро найти. В программировании «документы» — это данные (числа, строки, объекты), а «полки» — это массивы, списки, деревья, хеш-таблицы и т. д. Почему это важно: от выбора структуры часто зависит скорость операций (поиск, вставка, удаление) сильнее, чем от выбора самого алгоритма. Грубо говоря, плохая структура данных превращает любой алгоритм в тормоз, а хорошая — делает даже простой код молниеносным.

Связка «правильный алгоритм + правильная структура данных» — это то, что превращает медленную программу в быструю. Один и тот же набор операций может работать за секунды или за часы — и разница почти всегда определяется не языком программирования, а тем, как организованы данные и как описаны шаги обработки.

Алгоритмы и структуры данных — это ядро любой программы и главный фильтр на экзаменах по программированию в МИФИ, МГУ (ВМК) и МФТИ (ФПМИ). Без них код превращается в формулу «работает на маленьком примере, но зависает на реальных данных»: например, поиск по списку из миллиона элементов за O(n) вместо O(log n) — это разница между секундой и часом ожидания (≈ 1 секунда против ≈ 3600 секунд при n = 10⁶, потому что log₂(10⁶) ≈ 20).

Именно поэтому на собеседованиях и экзаменах в этих вузах проверяют не знание синтаксиса конкретного языка, а умение:

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

Эти навыки переносятся между C, C++, Python и Java — синтаксис меняется, а паттерны мышления остаются. Именно их и проверяют на серьёзных собеседованиях в Яндексе, Google, Тинькофф и других IT-компаниях: кандидат, который путает стек и очередь или не может оценить сложность рекурсивного решения, не пройдёт отбор, даже если идеально знает синтаксис Python.

Здесь собрано то, что реально спрашивают на зачётах и коллоквиумах:

• Оценка сложности (O-нотация) — это «как быстро растёт время работы при росте объёма входных данных». Именно по ней преподаватель сразу видит, понимаете ли вы алгоритм или просто заучили код. Практический смысл: O(n) при n = 10⁶ — это миллион операций (миллисекунды), O(n²) — это триллион (часы). Если алгоритм квадратичный, его не спасут ни быстрый процессор, ни оптимизирующий компилятор — при росте n он всё равно проиграет логарифмическому. Типичный подвох на экзамене: студенты путают O(log n) и O(n) на маленьких n (оба «быстрые» при n < 1000), но на n = 10⁹ разница становится космической.
• Линейные структуры:
  • Массив — «ряд пронумерованных ячеек с мгновенным доступом по индексу за O(1)». Классический пример — список студентов в журнале: чтобы найти i-го студента, не нужно перебирать всех, достаточно открыть страницу с нужным номером. Плюсы: компактность, кэш-дружелюбность (данные лежат подряд в памяти), быстрый доступ. Минусы: вставка/удаление в середине — дорого, за O(n), потому что нужно сдвигать хвост, как учеников в строю, когда один пересаживается.
  • Связный список — «поезд из вагонов: каждый вагон хранит данные и ссылку на следующий, поэтому вставка в середину дёшева — достаточно перецепить два указателя, как прицепляют вагон к составу». Плюсы: динамический размер, O(1) на вставку/удаление при известной позиции. Минусы: нет произвольного доступа (нужно идти от головы каждый раз), лишний расход памяти на указатели, плохая локальность данных (кэш процессора не помогает).
• Хеш-таблицы — обеспечивают мгновенный поиск по ключу в среднем за O(1), как поиск слова в словаре по буквам, без перелистывания страниц. Почему это работает: специальная функция (хеш-функция) превращает ключ в индекс массива за одно вычисление, и нужная ячейка находится сразу — вы приходите прямо к полке, не обходя весь склад. Главная ловушка: в худшем случае (при плохой хеш-функции или при атаке специально подобранными ключами) сложность падает до O(n), поэтому на экзамене всегда спрашивают, как обрабатывать коллизии (метод цепочек vs открытая адресация) и почему важна криптостойкая хеш-функция.
• Сбалансированные деревья (AVL и красно-чёрные) — это «бинарный поиск, который сам себя перестраивает после каждой вставки, чтобы высота оставалась логарифмической». Зачем это нужно: обычное бинарное дерево поиска в худшем случае вырождается в линейный список (если данные приходят отсортированными — представьте, что вам подсовывают ключи 1, 2, 3, 4, 5, и дерево растёт только вправо), и поиск превращается в O(n). Самобалансирующиеся деревья гарантируют O(log n) в худшем случае — это «страховка» от вырождения, как система стабилизации в автомобиле, которая выравнивает машину даже на скользкой дороге.
• Сортировки: от пузырька O(n²) до быстрой (Хоара) и пирамидальной O(n log n). Разница в десятки раз на миллионе элементов: пузырёк на n = 10⁶ — это примерно 10¹² операций (часы), а быстрая сортировка — около 2·10⁷ операций (доли секунды). Практический совет: в реальных проектах почти всегда используют встроенную qsort / std::sort, но на экзамене часто просят написать сортировку руками (особенно сортировку слиянием — она стабильна, имеет гарантированное O(n log n) и легко доказывается по индукции). Типичная ошибка: забыть, что быстрая сортировка в худшем случае даёт O(n²) — на отсортированных данных без рандомизации она деградирует, и это любимый вопрос преподавателей.
• Строковые алгоритмы (КМП и Z-функция) — поиск подстроки как поиск рифмы в стихотворении за линейное время, без возвратов. Идея: вместо того чтобы «откатываться» при несовпадении (как наивный поиск, который каждый раз начинает сначала), эти алгоритмы запоминают длину уже совпавшего префикса и сразу перескакивают на нужную позицию, экономя сравнения. Результат — O(n + m) вместо O(n·m). Зачем это нужно: в задачах с длинными текстами и множеством запросов (поиск по логам, биоинформатика) наивный алгоритм просто не успеет отработать за отведённое время.
• Графы:
  • BFS (поиск в ширину) — обход как волна по поверхности воды: сначала все ближайшие соседи, потом соседи соседей, и так далее. Используется для поиска кратчайшего пути в невзвешенном графе (где все рёбра равноценны, как этажи здания).
  • DFS (поиск в глубину) — обход как движение по лабиринту: идём вглубь до упора, потом возвращаемся (откатываем стек) и пробуем следующий коридор. Используется для топологической сортировки (порядок выполнения задач с зависимостями), поиска циклов, компонент связности.
  • Алгоритм Дейкстры — прокладка кратчайшего маршрута по карте города с положительными весами рёбер. Ловушка №1: не работает с отрицательными весами (для них нужен Беллман-Форд) — нельзя «подарить» водителю деньги, чтобы проехать по дороге. Ловушка №2: если забыть про приоритетную очередь, алгоритм скатится с O((n + m) log n) до O(n²), что на больших графах будет заметно.
• Динамическое программирование — разбиение задачи на перекрывающиеся подзадачи по принципу «посчитал один раз, запомнил ответ в таблице, переиспользовал вместо повторного вычисления». Классический пример: числа Фибоначчи — наивная рекурсия даёт O(2ⁿ) (каждое число считается заново по экспоненте), а DP с массивом — O(n) (каждое значение вычисляется ровно один раз). Главные шаги DP: 1) определить состояние (что хранить в dp[i]); 2) записать переход (рекуррентное соотношение, связывающее dp[i] с предыдущими); 3) задать базу (начальные значения); 4) выбрать порядок обхода (снизу вверх через цикл или сверху вниз через рекурсию с мемоизацией). Подводный камень: решение «в лоб» без чёткого состояния превращает DP в спагетти-код, который невозможно отладить.

Каждая тема дана по одной и той же схеме, которая проверена годами подготовки и лекторами сильнейших вузов:

• Идея простыми словами — чтобы понять суть без зубрёжки и сухих формул. Начинайте именно с этого блока: если не можете объяснить алгоритм другу на пальцах за минуту, вы его не поняли, а просто заучили. Преподаватель на устном экзамене начнёт с вопроса «а в чём суть?» — и если вы не можете ответить своими словами, дальше будет больно.
• Операции и сложность — чтобы знать, когда какую структуру применять, и не попасть в ловушку «вроде работает, но на 10⁶ элементах тормозит». Запомните таблицу «операция → сложность» как таблицу Менделеева — на экзамене она должна отскакивать от зубов. Практический навык: берите любую задачу и сначала оценивайте сложность до написания кода — это дисциплинирует и спасает от переделок.
• Компактный код на C или C++ с комментариями — чтобы увидеть живую реализацию, а не абстрактное описание из учебника. На экзамене часто просят написать код от руки, без IDE и подсветки, поэтому тренируйтесь набирать код по памяти и проговаривать каждую строку. Совет: заведите себе «карточки» — на одной стороне условие задачи, на другой — готовое решение; периодически прорешивайте их как настоящие экзаменационные билеты.
• Случай применения — чтобы привести конкретный пример из жизни, а не выдуманную абстракцию: «очередь — это как очередь в столовой, стек — как стопка тарелок». Преподаватели любят такие объяснения и ставят за них бонусные баллы. Что запомнить: очередь — FIFO (первый пришёл — первый ушёл), стек — LIFO (последний положил — первый взял). Если перепутать в задаче — гарантированная ошибка.
• Вопросы с ответами по вузам — у каждого вуза свой стиль, и это важно учитывать при подготовке:
  • МИФИ любит формальные оценки сложности и разбор краевых случаев (что будет при n = 0, при пустой строке, при единственном элементе). Будьте готовы строго доказать, что ваш алгоритм работает за O(n log n), а не «примерно так».
  • ВМК МГУ — строгие доказательства корректности и нестандартные модификации классических алгоритмов. Здесь часто дают «сломать» стандартный алгоритм: например, что будет, если в пирамидальной сортировке заменить sift-down на sift-up?
  • ФПМИ МФТИ — задачи повышенной сложности и олимпиадный уклон: комбинированные структуры данных, неочевидные применения DP, сложные графы.
  • Совет: готовьтесь под конкретный вуз, а не «в среднем» — разница в стилях реальна и заметна на экзамене.
• План подготовки на 7 дней — чтобы не утонуть в материале и распределить время между темами с учётом кривой забывания Эббингауза: первое повторение через 20–30 минут после изучения, второе — через день, третье — через неделю. Без повторений вы забудете ~60% нового материала за сутки, ~75% за неделю и ~90% за месяц. Практический приём: после прочтения темы отложите шпаргалку и через 15 минут перескажите её содержимое по памяти — то, что не смогли вспомнить, и есть ваши «дыры».
• Таблица частых ошибок — типичные грабли, на которые наступают даже сильные студенты:
  • Путаница O(n²) и O(n log n) — на n = 10⁶ это разница в ≈ 50 000 раз. Проверяйте асимптотику всегда, даже если кажется, что «и так сойдёт». Привычка считать сложность до кода — половина успеха на собеседовании.
  • Забытый +1 в границах массива (off-by-one) — классика жанра. Всегда проверяйте цикл на пустом массиве (n = 0) и на массиве из одного элемента (n = 1) — это ловит 90% ошибок с границами. Правило: пишите инвариант цикла (что истинно перед началом и после каждой итерации) — он сразу выявляет, где граница сдвинута на единицу.
  • Бесконечная рекурсия без базы выхода — стек вызовов переполняется, программа падает с Stack Overflow. Правило: в любой рекурсивной функции первая строка — проверка условия выхода (базы), и эта строка должна срабатывать при всех допустимых входных данных.
  • Переполнение стека при глубокой рекурсии — для деревьев на n = 10⁵ рекурсивный обход может упасть, потому что каждый вызов «ест» десятки байт под локальные переменные и адрес возврата. Если глубина рекурсии пропорциональна n, лучше переписать алгоритм через собственный явный стек (цикл + массив/вектор).
  • Использование == вместо = в условии (if (a = b) вместо if (a == b)) — компилятор C/C++ молча присвоит значение, и условие станет логическим значением b. Защита: включайте предупреждения -Wall -Wextra (компилятор предупредит -Wparentheses), а в спорных случаях пишите «yoda-условие» — if (5 == x) — ошибку в нём сделать синтаксически невозможно.
  • Утечка памяти в C при ручном malloc/free — каждый malloc должен иметь парный free ровно один раз на каждом пути выполнения (включая ветки с return, с обработкой ошибок и исключениями). Инструменты: valgrind (классика для Linux), AddressSanitizer (-fsanitize=address в GCC/Clang), LeakSanitizer. На экзамене проверяющий может намеренно дать задачу, где нужен free, и отсутствие освобождения — гарантированный минус.

Главная ловушка студента: не пытайтесь прочитать шпаргалку залпом от корки до корки — это рецепт перегореть и забыть всё к экзамену. Исследования когнитивной психологии показывают, что при пассивном чтении усваивается не более 10–15% материала, а при активном решении задач — до 70–80%. Поэтому:

Держите страницу открытой во время подготовки и возвращайтесь к нужному разделу по мере прохождения курса. Не читайте всё подряд: прочитали про массивы — порешали задачи на массивы, прочитали про списки — порешали на списки, прочитали про графы — порешали на графы. Именно так мозг формирует нейронные связи между новой информацией и уже известными паттернами, и именно так теория превращается в навык.

Решайте задачи руками — сначала на бумаге (это задействует моторную память и заставляет думать без подсказок IDE, автодополнения и подсветки ошибок — ровно как на настоящем экзамене), потом в редакторе (чтобы проверить, что код компилируется и работает на тестах). Проговаривайте сложность вслух — это заставляет формулировать мысль точно и сразу выявляет пробелы: если не можете сказать «это работает за O(n log n), потому что…», значит, вы не понимаете алгоритм, а только имитируете понимание. Сверяйте с эталоном — после решения сравните с эталонным кодом и эталонной оценкой сложности; разберите, почему эталон лучше: может, он экономнее по памяти, или использует более подходящую структуру данных, или обрабатывает граничный случай, который вы пропустили.

Алгоритмы учатся не пассивным чтением, а написанием кода, разбором чужих ошибок и анализом собственных. Типичная ошибка подготовки: решил пять задач по сортировкам → «я понял тему» → на экзамене не могу вспомнить, какую сортировку когда применять и в чём разница между устойчивой и неустойчивой. Решение: после каждой темы составляйте табличку-сводку на одном листе (структура / операция / сложность / когда применять / типичные ошибки) и перерисовывайте её перед экзаменом от руки. Кривая забывания работает против вас: без активного повторения через 1 день вы забудете ~60% деталей, через неделю — ~75%.

Через неделю такой подготовки вы заметите, что условие задачи с экзамена читается уже не как китайская грамота, а как набор знакомых паттернов, которые достаточно собрать в правильном порядке. Это и есть главный навык — не заучивание кода, а распознавание паттернов и их комбинирование: увидели «подстрока в строке» — в голове сразу алгоритм КМП; увидели «кратчайший путь с положительными весами» — сразу Дейкстра; увидели «разбить на подзадачи с перекрытием» — сразу DP. Это умение не появляется само — оно тренируется ежедневным решением и обязательным разбором ошибок, своих и чужих.

Ключевые термины

Что проверяют по алгоритмам (по вузам)

Алгоритмы и структуры данных — это базовый раздел информатики. Простыми словами: алгоритм — это пошаговый рецепт решения задачи (как кулинарный рецепт: «возьми яйца, разбей, смешай, поставь в духовку на 180°»). Структура данных — это способ организации информации в памяти компьютера (как полки в шкафу: обувь лежит на одной полке, книги — на другой, иначе всё смешается и найти нужное будет долго). Курс учит выбирать правильную «полку» и правильный «рецепт», чтобы программа работала быстро и не тратила лишнюю память.

Формально курс называется по-разному, но ядро (то есть набор тем, который встречается почти везде) почти совпадает: сложность, структуры данных, сортировки, деревья и графы. Различия между вузами — в глубине и в акценте на теории. Именно поэтому в таблице ниже собраны именно опорные темы, а не полный список экзаменационных билетов.

Что важно понимать: в МИФИ чаще требуют аккуратную реализацию базовой структуры «вручную» — преподаватель хочет убедиться, что вы понимаете, как список или стек «живёт» в памяти, умеете работать с указателями и не «прячетесь» за готовыми контейнерами STL. МГУ любит доказывать оценки сложности и разбирать вырожденные случаи (например, что будет с быстрой сортировкой Хоара, если массив уже отсортирован и опорный элемент выбран неудачно — сложность деградирует до O(n²)). МФТИ — комбинировать структуру с алгоритмом (например, Дейкстра на куче: очередь с приоритетом становится частью алгоритма кратчайшего пути, и без неё получится медленное O(n²) решение вместо O((n+m) log n)). Поэтому готовиться стоит не к «своему» вузу, а к общему ядру: один раз выучив идею и сложность, вы отвечаете в любом формате.

Практические советы при подготовке:

• Сначала разберитесь в идее алгоритма на простом примере (даже на бумаге: нарисуйте 5–7 чисел, пройдите алгоритм по шагам), и только потом переходите к коду. Так код запоминается сам.
• Запоминайте не сам код, а контракт алгоритма: что на входе, что на выходе и какова сложность по времени и памяти (O-нотация). Этого хватает для 80% устных вопросов.
• Умейте объяснить алгоритм тремя способами: словами (что делаем), кодом (как пишем), картинкой (как выглядит граф/дерево/массив на каждом шаге). Преподаватели обычно просят хотя бы два из трёх.

Типичные ошибки студентов:

• Путать сложность «в среднем» и «в худшем случае». Например, быстрая сортировка: O(n log n) в среднем, но O(n²) в худшем. Если на экзамене говорят «быстрая сортировка работает за O(n log n)» — это неполный ответ, нужно уточнить «в среднем случае».
• Забывать про вырожденные случаи: пустой массив, один элемент, все элементы одинаковые, уже отсортированный массив. Любой уважающий себя преподаватель подкинет именно такой тест-кейс, чтобы проверить, что ваш код не падает и не зацикливается.
• Декламировать код «наизусть», не понимая, почему он работает. Преподаватели это видят за минуту — достаточно задать один уточняющий вопрос («а что будет, если поменять знак сравнения?»), и всё рассыпается. Лучше понимать логику и восстанавливать код на месте, чем зубрить чужое решение.

Оценка сложности (O-нотация)

Что это такое (простое определение). Сложность описывает, как быстро растёт время работы алгоритма (или расход памяти) при увеличении размера входных данных n. Это не точное время в секундах, а характер поведения алгоритма «в пределе», когда данных становится очень много.

Аналогия из жизни. Представь, что ты готовишь обед для гостей. Если ты просто добавляешь по одной минуте на каждого нового гостя — это рост O(n). А если каждый гость должен попробовать каждое блюдо у всех остальных — это уже O(n²): при 10 гостях нужно ~100 проб, а при 100 — уже ~10 000. Сложность как раз говорит, в какой «истории роста» мы окажемся.

Главное правило: константы и младшие степени отбрасываются, важна только старшая растущая часть. Это потому, что при больших n именно старшая степень определяет поведение — константы и слагаемые становятся «шумом» по сравнению с ней. Например, 3n² + 5n + 100 при n = 10⁶ превращается практически в 3·10¹², а всё остальное теряется на её фоне.

• O(f(n)) — верхняя граница: алгоритм растёт не быстрее чем f(n). Это «гарантия, что хуже не будет». Если написано O(n²), реально алгоритм может работать и за O(n), но точно не за O(n³).
• Ω(f(n)) — нижняя граница: алгоритм растёт не медленнее чем f(n). Это «хорошего результата ждать не стоит» — даже в лучшем случае медленнее этой функции не получится.
• Θ(f(n)) — точная оценка: одновременно и O, и Ω — означает, что и сверху, и снизу функция ограничена одной и той же f(n). Это самая сильная и информативная оценка.

Зачем это нужно (почему так). Нам важна не точная формула с константами, а характер поведения алгоритма на больших данных. Сравнение «что лучше — 100n или n²?» даёт разные ответы при n = 10 и при n = 10⁹, но асимптотика сразу говорит: 100n всегда выиграет у n² (для достаточно больших n). Это позволяет сравнивать алгоритмы вне зависимости от железа и языка программирования.

Как читать запись на практике. O(n) — «линейно», O(log n) — «почти мгновенно даже на миллиарде элементов», O(n²) — «опасно на больших n», O(2ⁿ) — «работает только до n ≈ 25», O(n!) — «исключительно для крошечных n».

Как считать на экзамене:

• Последовательные блоки складываются, берётся максимум: O(n) + O(n²) = O(n²). Логика: всё равно доминирует самая «тяжёлая» часть — остальные блоки не меняют общий порядок роста. Пример: сначала один проход по массиву, потом двойной цикл — общее время всё равно определяется двойным циклом.
• Вложенные циклы перемножаются: два цикла по n дают O(n²). Почему: внешний выполняется n раз, и на каждой итерации внутренний тоже делает n шагов, итого n·n = n². Три вложенных цикла — O(n³).
• Цикл «делитель пополам» даёт O(log n): while (n > 1) n /= 2;. Аналогия: каждый шаг отбрасывает половину работы, как в игре «угадай число от 1 до 1000» — нужно всего ~10 вопросов, потому что каждый раз диапазон сокращается вдвое. То же самое даёт умножение индекса на 2 в каждой итерации: for (i = 1; i < n; i *= 2).
• Рекурсию оценивают по рекуррентности. Для T(n) = 2T(n/2) + O(n) (сортировка слиянием) ответ O(n log n) — это основная теорема о рекуррентностях (Master Theorem). Здесь две половинки задачи и работа O(n) на каждом уровне, таких уровней log n, итого n log n. Для T(n) = T(n/2) + O(1) (бинарный поиск) — O(log n): одна половинка и константная работа на уровень. Для T(n) = 2T(n/2) + O(1) (обход дерева) — O(n): на каждом из log n уровней суммарно делается константная работа, но из-за того, что узлов всего n, получается линейный обход.
• Амортизированная сложность — среднее время на операцию в худшей последовательности операций. Пример: push_back у std::vector — O(1) амортизированно, потому что редкое расширение буфера (которое само по себе O(n)) оплачивается множеством дешёвых вставок. Считается так: каждая вставка «вкладывает» немного денег в копилку, и когда буфер расширяется, эти деньги оплачивают копирование. Гарантия работает для любой последовательности, а не в среднем по случайным данным.

Практические подсказки для экзамена:

• Если видишь if, print, +=, одиночные арифметические операции — это O(1).
• Цикл for (i = 0; i < n; i++) — это O(n).
• Деление индекса или n пополам (n /= 2, i /= 2) — это log.
• Двойной вложенный цикл по n — это n². Тройной — n³.
• Не пытайся считать точно — просто определи «порядок» (самую быстрорастущую часть).
• Если есть if внутри цикла — сложность всё равно остаётся O(n), потому что if это O(1) и не умножается на n.
• Если внутри цикла вызывается функция с O(log n), общая сложность — O(n log n), не O(n).

Типичные ошибки:

• Путать «среднее» и «амортизированное». Среднее — это матожидание при случайных данных, а амортизированное — гарантия для любой последовательности операций. push_back амортизированно O(1) — это не «в среднем», а «в самом худшем случае для последовательности».
• Считать O(2n) ≠ O(n). Две одинаковые операции подряд — это всё ещё O(n), константа 2 отбрасывается.
• Складывать вложенность. Если один цикл O(n) вложен в другой O(n), получается O(n²), а не O(2n) и не O(n). Умножение, не сложение.
• Забывать про худший случай. Алгоритм быстрой сортировки — O(n log n) в среднем, но O(n²) в худшем (плохой выбор опорного элемента).

Как пользоваться таблицей. Смотри на колонку n = 1000 — она примерно показывает, насколько быстро «деградирует» алгоритм. O(1) и O(log n) остаются крошечными, O(n²) уже миллион, а O(2ⁿ) взрывается так быстро, что даже не помещается в разумные пределы. Числа для n = 100 у O(2ⁿ) (~10³⁰) — это больше, чем атомов на Земле.

Практический ориентир по времени: на современном CPU за секунду выполняется порядка 10⁸–10⁹ простых операций. Значит, при n = 10⁵ допустимо O(n log n) (≈ 1.7·10⁶ операций — уложится с большим запасом), но не O(n²) (10¹⁰ операций — это уже ~10–100 секунд, не уложится). На экзамене часто просят именно это рассуждение: «уложится ли решение в лимит». Если в условии n ≤ 10⁵ и TL = 1 секунда — выбирай O(n log n) или O(n), но не O(n²).

Мини-таблица «что пройдёт за 1 секунду» (полезно держать в голове):

• n ≤ 10⁷ → O(n) пройдёт
• n ≤ 10⁵ → O(n log n) пройдёт
• n ≤ 10⁴ → O(n²) пройдёт
• n ≤ 500 → O(n³) пройдёт
• n ≤ 25 → O(2ⁿ) пройдёт
• n ≤ 12 → O(n!) пройдёт

Типичные ошибки на практике:

• Забывать про ввод-вывод. В C++ cin >> x может быть настолько медленным, что «O(n)»-решение не пройдёт по времени из-за ввода. В таких случаях используют scanf/printf или в начале main пишут ios_base::sync_with_stdio(false); cin.tie(NULL);.
• Игнорировать размер стека. Рекурсивные алгоритмы с глубиной O(n) (например, наивный fib(n) через две рекурсии) могут упасть по переполнению стека ещё до того, как сработает ограничение по времени.
• Считать, что C++ всегда быстрый. Сложность алгоритма важнее микрооптимизаций: переход с O(n²) на O(n log n) даст в тысячи раз больший выигрыш, чем любые трюки с указателями и ручным управлением памятью.

Структуры данных

Для каждой структуры ниже: идея, ключевые операции, сложность, компактный код и типичная ситуация применения. Это тот минимум, который спрашивают на любом экзамене.

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

Массив и динамический массив

Что это? Массив — это непрерывный блок (кусок) памяти, в котором элементы лежат друг за другом без промежутков. Именно благодаря непрерывности доступ по индексу работает за O(1) — адрес i-го элемента вычисляется как base + i * sizeof(тип). Процессору не нужно ничего искать: он просто прибавляет смещение к началу блока. Это как квартал домов с номерами 1, 2, 3, ... — чтобы найти дом №i, достаточно знать, где стоит дом №1, и размер одного дома.

Статический массив фиксирован при создании, а динамический массив (в C++ — std::vector) сам расширяется по мере надобности. Когда место заканчивается, он выделяет буфер вдвое большего размера и копирует туда все данные. Старый буфер освобождается. Поэтому итоговая стоимость одной вставки — O(1), но амортизированно: одна редкая вставка стоит O(n) (копирование), зато следующие n вставок — снова O(1).

// Динамический массив на чистом C: рост в 2 раза
#include <stdlib.h>

typedef struct {
    int *data;
    size_t size;      // сколько занято
    size_t capacity;  // сколько выделено
} Vector;

void push(Vector *v, int value) {
    if (v->size == v->capacity) {
        size_t cap = v->capacity ? v->capacity * 2 : 4;   // амортизация O(1)
        int *tmp = realloc(v->data, cap * sizeof *tmp);
        if (!tmp) abort();
        v->data = tmp;
        v->capacity = cap;
    }
    v->data[v->size++] = value;
}

Почему так? Доступ по индексу — O(1), потому что адрес считается арифметически. Вставка в середину — O(n), потому что нужно сдвинуть хвост массива вправо (представьте очередь в магазине: если человек в середине уходит, все остальные за ним делают шаг вперёд). Поиск значения — O(n), потому что массив не знает, где искомое: в худшем случае надо просмотреть все элементы.

Подсказки:

• Начинайте ёмкость с 4, а не с 1 — меньше аллокаций в начале.
• Коэффициент роста ×2 — золотая середина между частотой аллокаций и расходом памяти (максимум ~33% «лишней» памяти).
• Если заранее известен размер — зарезервируйте через reserve() / realloc(), чтобы избежать копирований.

Типичные ошибки:

• Забыть сохранить указатель, возвращённый realloc (при неуспехе старая память остаётся валидной — её обязательно нужно освободить).
• Использовать sizeof(int*) вместо sizeof *tmp — выделите в разы меньше памяти.
• Думать, что амортизированное O(1) гарантирует жёсткое O(1) — в худшем случае одна вставка действительно стоит O(n).

Применение: когда нужен быстрый произвольный доступ и данные читаются/пишутся в основном в конец. Это основа почти всех остальных структур: стек, очередь, хеш-таблица, динамические строки — внутри у них массив.

Связный список

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

Память не обязана быть непрерывной, поэтому вставка и удаление при уже известном узле стоят O(1) — достаточно перекинуть пару указателей. Плата — нет произвольного доступа: чтобы добраться до i-го элемента, нужно пройти все предыдущие. Двусвязный список хранит ещё и указатель на предыдущий узел, что позволяет удалять узел без обхода (важно для std::list и реализации LRU-кешей).

// Односвязный список: вставка в начало
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *push_front(Node *head, int value) {
    Node *n = malloc(sizeof *n);
    if (!n) return head;
    n->value = value;
    n->next = head;
    return n;                 // новый head
}

void free_list(Node *head) {
    while (head) { Node *next = head->next; free(head); head = next; }
}

Почему так? Указатели лежат в разных местах памяти, и процессор каждый раз обращается к новой ячейке — отсюда линейный доступ. Зато чтобы вставить узел, не нужно никого сдвигать: меняем два указателя — и всё. У односвязного списка есть тонкость: чтобы удалить узел, нужно знать предыдущий узел (иначе хвост «потеряется»), поэтому пишут O(1) после prev. В двусвязном списке prev уже есть в самом узле.

Подсказки:

• Всегда сохраняйте указатель next до free(head) — иначе потеряете остаток списка (классическая утечка на ровном месте).
• Для двусвязного списка обновляйте четыре указателя при вставке/удалении — забытый один превращает структуру в мусор.
• Не используйте связный список там, где много случайного доступа — это его главная слабость.

Типичные ошибки:

• Смешивать «знаю узел» и «знаю индекс»: найти узел по индексу — это O(n), и только сама вставка/удаление — O(1).
• Забыть head = head->next при обходе и ходить по кругу вечно (бесконечный цикл).
• Не обнулить указатель удалённого узла — получите use-after-free.

Применение: очередь, LRU-кеш, структуры с частыми вставками и удалениями в середине. На экзамене любят вопрос «почему список не даёт бинарного поиска» — потому что нет произвольного доступа: нельзя за O(1) прыгнуть в середину, а значит, нельзя и делить диапазон пополам.

Стек

Что это? Стек — структура LIFO (Last In — First Out): последним положили — первым достали. Представьте стопку тарелок: вы кладёте тарелку сверху и берёте тоже только сверху. Операции push (положить) и pop (снять) работают за O(1).

Проще всего реализуется массивом с индексом вершины — непрерывная память, быстрый доступ, минимум кода. Системный стек вызовов (call stack), куда попадают адреса возврата и локальные переменные при вызове функций, устроен ровно так же. Поэтому переполнение стека вызовов (stack overflow) — это та же ошибка, что и переполнение нашего ручного стека.

// Стек на массиве фиксированной ёмкости
#define STACK_MAX 1000

typedef struct {
    int data[STACK_MAX];
    int top;              // индекс вершины, -1 — пусто
} Stack;

void init(Stack *s)   { s->top = -1; }
int  empty(Stack *s)  { return s->top < 0; }
void push(Stack *s, int v) { if (s->top + 1 < STACK_MAX) s->data[++s->top] = v; }
int  pop(Stack *s)    { return empty(s) ? -1 : s->data[s->top--]; }

Почему так? Все операции — на одном конце массива (на вершине), указатель top двигается только вверх или вниз. Никаких сдвигов, никакого поиска — отсюда O(1). Альтернативная реализация — на связном списке, но она тратит больше памяти на указатели.

Подсказки:

• Следите за переполнением: push в заполненный стек молча игнорирует элемент (как в примере) — в продакшене лучше возвращать код ошибки или бросать исключение.
• Для стека переменного размера в C++ берите std::vector или std::stack — он сам растёт.
• Стек — основа рекурсии: каждый вызов «кладёт» кадр на стек, каждый return — «снимает» его. Глубокая рекурсия = риск переполнения.

Типичные ошибки:

• Забыть, что top == -1 означает пустой стек, и проверять top == 0 (потеряете один элемент).
• Снимать элемент со стека в пустом — сначала всегда empty().
• Слишком жёсткий STACK_MAX без обработки переполнения — одна неудачная последовательность push, и данные теряются.

Применение: отмена действий (Ctrl+Z — это стек команд), обход в глубину (DFS), проверка скобочной последовательности, вычисление выражений в обратной польской записи (постфиксной), обратный вывод пути в лабиринте.

Очередь

Что это? Очередь — структура FIFO (First In — First Out): первым положили — первым достали. Это как очередь в кассу: кто раньше встал, тот раньше уйдёт. В C++ готовая реализация — std::queue, которая обычно построена поверх std::deque.

На массиве её реализуют кольцевым буфером (ring buffer), чтобы pop не сдвигал все элементы влево — это было бы дорого. Идея: массив логически «склеен» в кольцо, и индексы head и tail движутся по кругу через % capacity. Освободившиеся ячейки в начале массива используются снова.

// Кольцевая очередь на массиве
class Queue {
    std::vector<int> buf;
    int head = 0, tail = 0, count = 0;
public:
    explicit Queue(int cap) : buf(cap) {}
    bool empty() const { return count == 0; }
    void push(int v) {                 // O(1)
        if (count == (int)buf.size()) return;   // переполнение
        buf[tail] = v;
        tail = (tail + 1) % (int)buf.size();
        count++;
    }
    int pop() {                        // O(1)
        if (empty()) return -1;
        int v = buf[head];
        head = (head + 1) % (int)buf.size();
        count--;
        return v;
    }
};

Почему так? В «наивной» реализации массива pop удалял бы первый элемент и сдвигал все остальные — это O(n). В кольцевом буфере head и tail просто перемещаются по кругу, и никаких сдвигов нет, поэтому обе операции — O(1). Счётчик count нужен, чтобы отличать «пусто» (count == 0) от «полно» (count == size) — без него head == tail означало бы оба состояния.

Подсказки:

• Кольцевой буфер хорош для фиксированного размера (например, очередь событий, аудиобуфер). Для переменного размера берите std::deque или std::queue.
• Если нужно уметь расти — реализуйте логику расширения, как в std::vector (выделить буфер больше, скопировать, пересчитать индексы).
• head и tail часто путают: head — откуда забираем, tail — куда кладём. Запомните по аналогии с кассой: «хвост» очереди прибывает, «голова» обслуживается.

Типичные ошибки:

• Использовать head == tail как признак пустоты — тогда нельзя отличить пустую очередь от полной. Нужен отдельный счётчик или флаг.
• Забыть % capacity — индексы «убегут» за границу массива, будет выход за пределы.
• При расширении кольцевого буфера забыть пересчитать head и tail относительно нового массива (типичная ошибка на собеседованиях).

Применение: обход в ширину (BFS), планировщик задач в ОС, обработка сетевых пакетов, буферизация данных между потоками, очередь печати, любой «конвейер», где важно сохранять порядок поступления. Применение: обход в ширину (BFS — послойный обход графа: сначала все вершины на расстоянии 1 от старта, затем на расстоянии 2 и т.д.), буферизация задач (временное хранение задач, когда обработчик не успевает принимать их в реальном времени), планировщики (компоненты ОС или приложения, решающие, какую задачу выполнить следующей), обработка событий (event loop — цикл, который забирает события из очереди и реагирует на них).

Дек

Что это? Дек (deque, сокращение от double-ended queue — «двусторонняя очередь») — это контейнер, который ведёт себя как очередь, но с двумя «выходами»: элементы можно добавлять и забирать как с начала, так и с конца, причём все эти операции работают за константное время O(1). В C++ это std::deque, в C — обычно реализуется через двусвязный список или кольцевой буфер.

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

Почему это важно? Обычная очередь (std::queue) разрешает работать только с одного конца, а вектор (std::vector) — эффективно только с конца (вставка в начало у вектора стоит O(n) из-за сдвига). Дек заполняет этот пробел: когда вам нужен «двухсторонний доступ» без штрафа за операции — это ваш выбор.

Классическое применение — скользящее окно с максимумом (монотонный дек).

#include <deque>

// Максимум в каждом окне размера k за O(n)
std::vector<int> windowMax(const std::vector<int> &a, int k) {
    std::deque<int> dq;                      // хранит индексы, значения убывают
    std::vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();   // ушло из окна
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();   // слабее нового
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

Как читать код. Дек здесь хранит индексы, а не значения — это типичный приём для задач на скользящее окно. Значения по этим индексам в массиве a образуют убывающую последовательность (отсюда название «монотонный дек»), поэтому на переднем плане (dq.front()) всегда индекс максимума текущего окна. Левый while выкидывает индексы, которые «выпали» из окна (стали меньше или равны i - k). Правый while удаляет с хвоста всех, кто «слабее» нового элемента — они уже никогда не станут максимумом, потому что новый элемент их перекрывает и при этом живёт в окне дольше.

Практический совет. Если вам не нужны обе стороны — предпочитайте std::vector (быстрее на чтение, лучшая кэш-локальность) или std::list/std::forward_list (если важны вставки в середину). Дек оправдан именно тогда, когда активно используются оба конца.

Типичные ошибки.

• Забыть выкидывать индексы, ушедшие за пределы окна — тогда максимум «застрянет» из прошлого и ответ окажется неверным.
• Сравнивать значения, а не индексы при проверке «вышел ли элемент из окна».
• Считать, что std::deque::operator[] даёт O(1) по времени в худшем случае — на практике доступ к произвольному элементу может быть чуть дороже, чем у вектора, из-за блочной внутренней структуры.
• Использовать дек там, где достаточно очереди или стека — это не страшно, но лишняя абстракция может сбить читателя кода.

Хеш-таблица

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

Аналогия из жизни. Это нумерованная гардеробная: вы сдаёте куртку (ключ — номерок), гардеробщик (хеш-функция) решает, на какую вешалку её повесить, а при выдаче по номерку мгновово находит нужную. Если две куртки претендуют на одну вешалку — возникает коллизия, и нужно как-то её разрешать: повесить обе на одну вешалку (цепочки) или сдвинуть вторую на соседнюю (открытая адресация).

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

Почему «в среднем O(1)»? Если хеш-функция распределяет ключи равномерно, каждая корзина содержит примерно n / m ключей (m — размер массива, n — число элементов). Это отношение называется коэффициент заполнения (load factor). Когда он становится слишком большим (обычно > 0.75), цепочки удлиняются и время доступа деградирует — именно поэтому делают перехеширование (rehash): создают новый массив вдвое больше и перекладывают все элементы заново, пересчитывая индексы по новому размеру.

// Хеш-таблица на цепочках: отдельная цепочка в каждой ячейке
class HashTable {
    struct Node { int key; int value; Node *next; };
    std::vector<Node *> buckets;
    int count = 0;
    size_t hash(int key) const { return std::hash<int>{}(key) % buckets.size(); }
public:
    explicit HashTable(size_t cap = 16) : buckets(cap, nullptr) {}
    void put(int key, int value) {
        size_t i = hash(key);
        for (Node *p = buckets[i]; p; p = p->next)
            if (p->key == key) { p->value = value; return; }
        buckets[i] = new Node{key, value, buckets[i]};
        if (++count > (int)buckets.size()) rehash();   // load factor > 1
    }
    int *get(int key) {
        for (Node *p = buckets[hash(key)]; p; p = p->next)
            if (p->key == key) return &p->value;
        return nullptr;
    }
    void rehash() {
        std::vector<Node *> old = std::move(buckets);
        buckets.assign(old.size() * 2, nullptr);
        count = 0;
        for (Node *head : old)
            for (Node *p = head; p;) { Node *n = p->next; put(p->key, p->value); delete p; p = n; }
    }
};

Как читать код. Внутри HashTable массив buckets — это вектор указателей на односвязные списки (цепочки). Новые узлы вставляются в голову списка — это самая дешёвая операция, не нужно идти до хвоста. При put сначала идём по цепочке: если ключ уже есть — обновляем значение, если нет — добавляем новый узел в голову. При rehash() мы переносим все узлы в новый массив в два раза больше и удаляем старые, потому что индексы (через % buckets.size()) теперь дают другие значения.

Практический совет. В реальном коде почти всегда лучше использовать std::unordered_map / std::unordered_set из стандартной библиотеки, чем писать свою хеш-таблицу: она оптимизирована, протестирована и поддерживает пользовательские хеш-функторы «из коробки». Самописная таблица оправдана только в учебных целях или узкоспециализированных задачах (например, когда нужен очень специфический аллокатор или особая схема роста).

Открытая адресация: при коллизии пробегаем последовательность ячеек. Линейное пробирование — (h + i) mod m, медленно «слипается». Квадратичное — (h + c₁i + c₂i²) mod m, лучше распределяет. Двойное хеширование — (h₁ + i·h₂) mod m, почти идеально. Удаление в открытой адресации помечает ячейку «удалённой» (tombstone), а не пустой, иначе рвётся цепочка поиска.

Почему «слипается» линейное пробирование? Если две соседние ячейки заняты, то любой ключ, чей хеш попадает между ними, тоже «уплывёт» дальше — образуются длинные кластеры занятых ячеек, и время поиска растёт (так называемая «первичная кластеризация»). Квадратичное пробирование и двойное хеширование разносят ключи шире и снижают этот эффект.

Худший случай возникает при плохой хеш-функции или целенаправленных коллизиях. Применение: словари, кеши, подсчёт частот, дедупликация.

Типичные ошибки.

• Использовать в качестве хеша саму величину ключа без модуля — элементы будут падать в узкий диапазон ячеек, цепочки перекосятся.
• Забыть про перехеширование — массив «забивается», цепочки вырастают, и время перестаёт быть O(1), деградируя до O(n).
• В открытой адресации удалять элемент как «пустой» — поиск сломается, потому что он использует пробирование и ему нужно «видеть», что ячейка когда-то была занята (отсюда tombstone — «надгробие»). Если в такой ячейке окажется «пусто», поиск остановится раньше времени и не найдёт ключ, который «прыгнул» дальше.
• Использовать нестабильный хеш (например, основанный только на адресе объекта в памяти) — два запуска программы дадут разные хеши, что сломает сериализацию/десериализацию и юнит-тесты, ожидающие детерминизма.
• Забыть про утечки памяти в самописной реализации на цепочках: new без delete (или без умных указателей) рано или поздно «съест» всю память.

Бинарная куча и priority_queue

Что это? Бинарная куча (binary heap) — это полное бинарное дерево (каждый уровень заполнен, кроме, возможно, последнего, и тот заполняется слева направо), в котором выполняется принцип кучи: значение в родителе «лучше» (меньше для min-heap, больше для max-heap), чем значения в его детях. Благодаря полноте дерево прекрасно укладывается в обычный массив без указателей.

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

Куча — полное бинарное дерево, хранимое в массиве: у узла i дети 2i+1 и 2i+2, родитель (i-1)/2. В min-heap родитель меньше детей, поэтому минимум всегда в корне. Вставка и извлечение корня — O(log n), чтение минимума — O(1).

Почему именно массив, а не узлы с указателями? Полное дерево без «дырок» можно компактно записать в массив: индексы вычисляются арифметически (2i+1, 2i+2, (i-1)/2), экономим память на указателях и получаем отличную кэш-локальность при обходе. Почему O(log n)? Высота полного дерева из n элементов — это ⌊log₂ n⌋, и все операции (вставка, удаление корня) спускаются максимум на эту глубину, «просеивая» элемент вниз или вверх.

#include <queue>
#include <vector>
#include <functional>

// min-heap: минимальный элемент на вершине
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
// max-heap (по умолчанию): максимальный элемент на вершине
std::priority_queue<int> maxHeap;

// Просеивание вниз в max-heap, хранимом в массиве
void siftDown(std::vector<int> &h, int i) {
    int n = (int)h.size();
    while (true) {
        int l = 2 * i + 1, r = 2 * i + 2, largest = i;
        if (l < n && h[l] > h[largest]) largest = l;
        if (r < n && h[r] > h[largest]) largest = r;
        if (largest == i) break;
        std::swap(h[i], h[largest]);
        i = largest;
    }
}

Как читать код. siftDown восстанавливает свойство кучи после того, как значение в позиции i стало «слишком большим» (нарушило max-heap порядок). На каждой итерации смотрим на двух детей, выбираем «лучшего» (для max-heap — большего) и, если он лучше родителя — меняем их местами. Цикл останавливается, когда родитель уже сильнее обоих детей или мы дошли до листа.

Практический совет. В std::priority_queue доступна только вершина (top()), извлечение — pop(). Чтобы получить и удалить минимум/максимум, пишите pq.top(); pq.pop(); (это два разных вызова, потому что pop() не возвращает значение — такова цена совместимости с контейнерами-адаптерами). Свой компаратор передаётся третьим аргументом шаблона.

Применение: очередь с приоритетом, алгоритм Дейкстры, k наибольших элементов, планирование задач.

Типичные ошибки.

• Пытаться обойти всю кучу подряд в порядке возрастания/убывания — это сломает свойство кучи. Куча не сортирует всё; она гарантирует только то, что минимум/максимум всегда в корне. Для полной сортировки нужны другие структуры или heap sort с извлечением подряд.
• Перепутать min-heap и max-heap: std::priority_queue по умолчанию — это max-heap (на вершине максимум). Для min-heap нужен std::greater<T> в качестве компаратора.
• Забыть, что priority_queue не поддерживает уменьшение ключа из коробки — это нужно реализовывать вручную (например, в алгоритме Дейкстры через отдельную структуру или «ленивое удаление»).
• Использовать кучу вместо отсортированного массива, если нужно много раз получать произвольный элемент по индексу — куча для этого не предназначена.
• Сравнивать производительность кучи через std::priority_queue (которая поверх std::vector + std::push_heap) с самописной кучей на указателях — последняя почти всегда проигрывает по кэш-локальности.

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

Что это? BST (Binary Search Tree) — это бинарное дерево, в котором для каждого узла выполняется инвариант: все ключи в левом поддереве строго меньше ключа узла, а все ключи в правом поддереве — строго больше. Благодаря этому поиск ключа похож на бинарный поиск в отсортированном массиве: на каждом шаге мы отбрасываем половину дерева.

Аналогия из жизни. Английский словарь или телефонный справочник: открываете посередине, смотрите первую букву слова, понимаете — идти влево или вправо, и так далее, пока не найдёте нужное слово. BST делает то же самое, только в виде дерева, а не плоского массива — это позволяет добавлять и удалять элементы дешевле, чем в отсортированном массиве.

BST — дерево, где у любого узла все ключи в левом поддереве меньше, а в правом больше. Это даёт поиск, вставку и удаление за O(h), где h — высота. Проблема: из отсортированной последовательности дерево вырождается в список и становится O(n).

Почему O(h), а не O(log n)? В сбалансированном BST высота действительно близка к log₂ n, и операции работают за O(log n). Но в несбалансированном дереве высота может вырасти до n (вырождение в «палку»/список), и тогда каждая операция становится линейной — фактически мы превращаем BST в односвязный список. Именно поэтому на практике чаще используют самобалансирующиеся деревья (AVL, красно-чёрные — на них построены std::set/std::map), а «голый» BST хорош в основном для обучения.

struct Node {
    int key;
    Node *left = nullptr, *right = nullptr;
    explicit Node(int k) : key(k) {}
};

Node *insert(Node *root, int key) {
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                       // дубликат: ничего не делаем
}

bool contains(Node *root, int key) {
    while (root) {
        if (key == root->key) return true;
        root = key < root->key ? root->left : root->right;
    }
    return false;
}

Как читать код. insert и contains спускаются по дереву, сравнивая ключ с текущим узлом: меньше — идём влево, больше — вправо. Если узла нет — это либо точка вставки (создаём новый Node), либо конец поиска (contains возвращает false). Дубликаты игнорируются — это стандартный выбор для множества; для мультимножества их нужно либо класть в специальный счётчик, либо отдельно обрабатывать «равно».

Практический совет. В продакшен-коде почти всегда лучше взять std::set / std::map (красно-чёрное дерево под капотом) или std::unordered_set / std::unordered_map (хеш-таблица). Самописный BST полезен для обучения и понимания рекурсии, но легко написать его с утечками памяти и трудно поддерживать балансировку вручную. Если всё же нужен BST как структура — рассмотрите std::unique_ptr<Node> и рекурсивные smart-указатели, либо идиому «pimpl».

Типичные ошибки.

• Забыть, что insert возвращает новое значение корня — в некоторых реализациях (особенно при рекурсивной вставке с перебалансировкой) корень может меняться, и эту «обновку» нужно сохранять: root = insert(root, key);.
• Не обработать удаление узла с двумя детьми — это самая сложная из базовых операций: нужно заменить ключ минимумом из правого поддерева (или максимумом из левого) и удалить уже того, кто «отдал» своё место. Без этого инвариант BST нарушается.
• Использовать BST как «универсальный контейнер» — для частого поиска по индексу (k-й элемент) лучше подходит декартово дерево по неявному ключу или Order Statistic Tree.
• Строить BST из отсортированной последовательности без балансировки — получится «палка», и всё преимущество O(log n) исчезнет, время деградирует до O(n).
• Забыть про утечки памяти: в C++ узлы создаются через new, и без умных указателей (std::unique_ptr<Node>) деструктор дерева нужно писать вручную с обходом в пост-порядке, иначе каждый удалённый узел оставит «хвост» в куче.
• Путать строгие и нестрогие сравнения (< против <=) — это влияет на то, как обрабатываются дубликаты и куда они кладутся в дерево.

  Дерево	Высота (среднее)	Высота (худшее)
  BST без балансировки	O(log n) при случайных данных	O(n) при вырожденных вставках
  AVL	O(log n)	O(log n)
  Красно-чёрное	O(log n)	O(log n)

Что такое «высота дерева»? Это длина (в рёбрах или узлах) самого длинного пути от корня до листа. Если высота O(log n), то поиск/вставка/удаление работают быстро, потому что каждый шаг отбрасывает половину (или хотя бы константную долю) элементов — как в двоичном поиске по массиву.

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

Обходы дерева — это способы посетить все узлы. Обход называется так по тому, в каком порядке посещаются корень и поддеревья:

• in-order (симметричный): левое поддерево → корень → правое поддерево. Для BST даёт ключи в порядке возрастания (как sort).
• pre-order (прямой): корень → левое → правое. Удобен для копирования/сериализации дерева: сначала записываем узел, потом его детей — структура сохраняется.
• post-order (обратный): левое → правое → корень. Нужен при удалении дерева: сначала освобождаем детей, потом сам узел, иначе потеряем указатели и получим утечку памяти.

АВЛ-дерево (повороты)

Определение. АВЛ-дерево — это бинарное дерево поиска (BST), у каждого узла которого высоты левого и правого поддеревьев отличаются не более чем на 1 (баланс-фактор ∈ {-1, 0, +1}). Названо в честь авторов: Адельсон-Вельский и Ландис (1962).

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

Почему именно |Δh| ≤ 1? Если разрешить перекос в 2, то при вставке в «глубокое» поддерево дисбаланс будет расти каскадно, и гарантии O(log n) уже не получится. А условие ≤ 1 — это минимальное жёсткое ограничение, которое ещё позволяет держать дерево логарифмической высоты.

Повороты — это «перевешивание» поддеревьев:

• LL (правый поворот) — перекос влево-влево: вставка в левое поддерево левого ребёнка. Нужно «поднять» левого ребёнка на место родителя.
• RR (левый поворот) — зеркально: перекос вправо-вправо.
• LR (двойной) — вставка в правое поддерево левого ребёнка. Сначала делаем левый поворот ребёнка (превращаем LR в LL), потом правый поворот родителя.
• RL (двойной) — зеркально к LR.

Нарушение баланса исправляется поворотами: одиночным (LL, RR) или двойным (LR, RL). Это гарантирует высоту O(log n).

struct AVLNode {
    int key, height = 1;
    AVLNode *left = nullptr, *right = nullptr;
    explicit AVLNode(int k) : key(k) {}
};

int height(AVLNode *n) { return n ? n->height : 0; }
int balance(AVLNode *n) { return n ? height(n->left) - height(n->right) : 0; }
void fix(AVLNode *n) { n->height = 1 + std::max(height(n->left), height(n->right)); }

AVLNode *rotateRight(AVLNode *y) {            // правый поворот (случай LL)
    AVLNode *x = y->left;
    y->left = x->right;
    x->right = y;
    fix(y); fix(x);
    return x;
}
AVLNode *rotateLeft(AVLNode *x) {             // левый поворот (случай RR)
    AVLNode *y = x->right;
    x->right = y->left;
    y->left = x;
    fix(x); fix(y);
    return y;
}

Подсказки по коду.

• В коде height — высота одного узла (в узлах), а не поддеревьев. Для пустого указателя возвращаем 0, поэтому у листа высота = 1 + max(0, 0) = 1.
• Функция fix (часто называют updateHeight) пересчитывает высоту узла после изменения детей.
• Порядок fix(y); fix(x); важен: сначала обновляем того, кто стал ниже (y), потом того, кто поднялся (x) — иначе высота будет неверной.

Как выбрать поворот на практике. Считаем balance(n) = height(left) - height(right).

1. Если balance > 1 (перевес влево) и balance(left) >= 0 → правый поворот (LL).
2. Если balance > 1 и balance(left) < 0 → сначала левый поворот левого ребёнка, потом правый (LR).
3. Если balance < -1 (перевес вправо) — симметрично: RR или RL.

При дисбалансе balance > 1 и ключ ушёл в левое поддерево левого ребёнка — нужен LL-поворот; если в правое поддерево левого — двойной LR (левый поворот ребёнка, затем правый поворот узла). Баланс при удалении может потребовать поворотов вверх до корня.

Типичные ошибки.

• Забыть обновить height у повёрнутых узлов — поиск потом «ломается».
• Использовать nullptr->height без проверки на nullptr — UB (undefined behavior).
• После поворота в поддереве не проверить баланс у предка — дисбаланс может подняться на уровень выше.
• Путать, когда нужен LR, а когда LL: смотрите не на дисбаланс родителя, а на то, в какое поддерево левого ребёнка ушла вставка.

Красно-чёрное дерево

Определение. Красно-чёрное дерево (Red-Black Tree, RBT) — самобалансирующийся BST, в котором каждый узел помечен одним из двух цветов (красный или чёрный) и выполняются пять инвариантов:

1. Корень — чёрный.
2. Каждый лист (NIL, «внешний» пустой узел) считается чёрным.
3. Если узел красный, то оба его ребёнка — чёрные (нет двух красных подряд).
4. Все пути от любого узла до его NIL-листьев содержат одинаковое число чёрных узлов (так называемая чёрная высота).
5. Каждый узел — либо красный, либо чёрный.

Аналогия. Это похоже на 2-3 дерево (B-дерево степени 2), где красный узел «склеен» со своим чёрным родителем в один 3-узел. Каждый инвариант отвечает за своё: правило 4 — за равномерность путей, правило 3 — запрещает «длинные цепочки» красных, которые удлинили бы путь.

Почему именно такие правила? Они дают компромисс: чёрная высота ≥ h/2, значит общая высота ≤ 2·log₂(n+1). Баланс не такой строгий, как в AVL, поэтому поворотов при вставке/удалении нужно меньше — но поиск чуть медленнее, потому что дерево может быть на ~40% выше.

Эти правила дают высоту не более 2·log₂(n+1). Балансировка мягче, чем в AVL, поэтому вставка и удаление чуть быстрее, а поиск чуть медленнее.

В C++ std::map и std::set реализованы именно на красно-чёрном дереве. Также на нём построены std::multimap, std::multiset. Причина выбора: операции чтения-записи встречаются вперемешку, и более дешёвая балансировка при записи окупается.

На экзамене обычно просят свойства и оценку высоты, а не полный код ребалансировки.

Подсказки.

• При подсчёте чёрной высоты не забывайте считать NIL-листья (они тоже чёрные по правилу 2).
• Если при удалении красный узел становится «чёрным с двойным уклоном» — используется «чёрный брат»-трюк с перекраской и поворотами (recolor).
• Балансировка при удалении сложнее, чем при вставке, — это частая «ловушка» в учебных задачах.

Типичные ошибки.

• Считать, что NIL-лист — это «ничего». Для корректности инвариантов каждый отсутствующий ребёнок заменяется виртуальным чёрным NIL-узлом.
• Путать красно-чёрное дерево с произвольной раскраской: цвета должны удовлетворять всем пяти правилам одновременно.
• Забыть перекрасить корень в чёрный в конце вставки.

Splay-дерево

Определение. Splay-дерево — самобалансирующийся BST, не хранящий в узлах никаких метаданных баланса (высот, цветов и т.п.). Вместо этого после каждой операции (поиск, вставка, удаление) узел, к которому обращались, «поднимается» в корень с помощью операции splay — последовательности поворотов. Получается дерево без явной балансировки, но с логарифмической сложностью в среднем (амортизированно).

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

Три вида поворотов при splay (относительно деда g, родителя p и узла x):

• Zig — x — ребёнок корня (нет деда): один обычный поворот.
• Zig-zig — x и p оба левые (или оба правые): сначала поворот вокруг g, потом вокруг p.
• Zig-zag — x — правый ребёнок левого p (или наоборот): сначала поворот вокруг p, потом вокруг g.

Почему амортизированная сложность O(log n)? Любая отдельная операция может стоить O(n) (если дерево вытянулось в линию). Но «плохая» операция заставляет splay «разровнять» дерево, и за ней идёт серия дешёвых. Усредняя по последовательности из m операций, получаем O(log n) на каждую. Это пример учётного метода (accounting method) в анализе алгоритмов.

// Идея splay: поднимаем узел x в корень поворотами
AVLNode *splay(AVLNode *root, int key) {
    if (!root || root->key == key) return root;
    if (key < root->key) {
        if (!root->left) return root;
        if (key < root->left->key) {                 // zig-zig (левый)
            root->left->left = splay(root->left->left, key);
            root = rotateRight(root);
        } else if (key > root->left->key) {          // zig-zag (левый)
            root->left->right = splay(root->left->right, key);
            if (root->left->right) root->left = rotateLeft(root->left);
        }
        return root->left ? rotateRight(root) : root;
    }
    // зеркально для правого поддерева
    return root;
}

Подсказки по коду.

• Функция возвращает указатель на новый корень — после splay это узел с ключом key (если он был).
• Рекурсивные вызовы splay(root->left->left, key) и т.п. — это «спуск» в нужное поддерево перед поворотами.
• Правая часть (key > root->key) в реальной реализации должна зеркально повторять логику для правого поддерева; тут она опущена для краткости.

Применение: кеши с временной локальностью, сетевые маршрутизаторы, реализация std::map без гарантий времени на отдельную операцию (амортизация).

Типичные ошибки.

• Считать, что splay-дерево даёт O(log n) в худшем случае — нет, только амортизированно. Для realtime-систем это критично.
• Забыть делать splay после поиска (даже если ключ не найден) — теряется смысл самобалансировки.
• Использовать splay в лексикографически отсортированных данных — есть атака сценариев, когда злоумышленник заставляет дерево каждый раз вытягиваться в линию.

Префиксное дерево (trie)

Определение. Trie (произносится «трай», от англ. retrieval — «поиск», иногда называют «бор») — дерево, в котором каждое ребро соответствует одному символу, а путь от корня до помеченного узла задаёт строку. В отличие от BST, trie не сравнивает строки целиком: оно идёт посимвольно, спускаясь по нужным рёбрам.

Аналогия из жизни. Представьте алфавитный указатель в энциклопедии: страницы сгруппированы по первой букве, внутри каждой группы — по второй и т.д. Точно так же trie: сначала идём по первой букве слова, потом по второй и т.д., пока не дойдём до конца.

Почему сложность O(L)? Где L — длина слова. Это не зависит от количества уже хранимых слов: мы идём по одной ветке фиксированной глубины L, а в каждом узле делаем O(1)-операцию (выбор ребёнка по символу). Для сравнения: в BST поиск слова — O(L · log n), потому что на каждом шаге мы сравниваем всё слово целиком.

Trie хранит строки посимвольно: путь от корня задаёт префикс, а флаг в узле отмечает конец слова. Поиск и вставка слова длины L — O(L) независимо от числа строк. Память может быть большой из-за пустых детей.

#include <string>

struct TrieNode {
    TrieNode *children[26] = {};   // только латиница в нижнем регистре
    bool terminal = false;
};

void insert(TrieNode *root, const std::string &word) {
    for (char c : word) {
        int idx = c - 'a';
        if (!root->children[idx]) root->children[idx] = new TrieNode;
        root = root->children[idx];
    }
    root->terminal = true;
}

bool search(TrieNode *root, const std::string &word) {
    for (char c : word) {
        root = root->children[c - 'a'];
        if (!root) return false;
    }
    return root->terminal;
}

Подсказки по коду.

• Массив children[26] — самый простой вариант для латиницы в нижнем регистре. Для общего случая используют std::unordered_map<char, TrieNode*> или массив из 256 (для байтов), или сжатие в std::array.
• Поле terminal важно: без него слова «ab» и «abc» выглядели бы одинаково. Именно оно отличает «узел, через который проходят слова» от «узла, который сам является концом слова».
• Вставка создаёт новые узлы только при необходимости (if (!root->children[idx])), поэтому повторные вставки префиксов дёшевы.

Практические оптимизации.

• Сжатие: хранить ветки как строки, а не по одному символу (Patricia-trie / radix-tree) — экономит память в 5–10 раз.
• Хэш-таблица вместо массива: для Unicode или большого алфавита (std::unordered_map<char, TrieNode*>).
• Удаление: нужно не только освободить узел, но и «схлопнуть» его, если после удаления у него не осталось детей и он не terminal.

Типичные ошибки.

• Забыть terminal = true в insert — поиск потом не находит слово, даже если узел существует.
• В search возвращать true, если узел существует, — без проверки terminal будет ложноположительный результат для префиксов (например, ищем «abc», а в дереве только «ab»).
• Считать, что trie сортирует строки. Он сохраняет лексикографический порядок при обходе, но не поддерживает операции вида «следующее по порядку» без дополнительной структуры.
• Игнорировать nullptr-доступ в search: если очередного ребёнка нет, нужно сразу вернуть false, не разыменовывая nullptr. Trie (префиксное дерево, бор) — это древовидная структура, в которой каждый узел хранит один символ (букву/цифру), а путь от корня до узла образует префикс или целое слово. Аналогия: представь словарь, в котором слова с общим началом «растут» из одной ветки — «кот» и «котлета» делят первые буквы и расходятся только в развилке. Главное преимущество — время операций зависит не от размера словаря, а от длины слова L: O(L) на вставку, поиск и удаление.

Применение: автодополнение (поиск слов по введённому префиксу в поисковиках, IDE и редакторах), словари (быстрая проверка наличия слова и его частоты), проверка префиксов (есть ли хоть одно слово, начинающееся с данной строки), IP-маршрутизация (поиск маршрута по битовому префиксу адреса в таблицах маршрутизации), задача о поиске слов на поле (trie + DFS) — например, в игре «Эрудит» или сканворде, когда нужно найти все слова, которые можно составить из букв на доске.

Система непересекающихся множеств (DSU / СНМ)

Определение. DSU (Disjoint Set Union, в русской литературе часто называют СНМ — «система непересекающихся множеств») — структура данных, которая хранит набор элементов, разбитых на несколько непересекающихся подмножеств. Для каждого элемента можно узнать, к какому множеству он относится (find), и объединить два множества в одно (union / unite).

Аналогия из жизни. Представь друзей в социальной сети, где у каждой группы есть «лидер» (представитель множества). Если два человека оказываются в одной группе, их лидеры «сливаются» — так мы понимаем, что вся группа теперь одна. Именно это и делает DSU.

Почему нужны две эвристики? Без оптимизаций дерево представителей может выродиться в цепочку длины n, и find будет работать за O(n). Сжатие путей (path compression) делает все пройденные вершины прямыми потомками корня, а объединение по рангу (union by rank) всегда подвешивает меньшее дерево к большему (или к равному). Вместе они дают почти константное время — амортизированно O(α(n)), где α — обратная функция Аккермана, растущая так медленно, что для всех практических n (даже для числа атомов во Вселенной, ~10⁸⁰) α(n) ≤ 5. Поэтому на практике DSU считают «почти O(1)».

struct DSU {
    std::vector<int> parent, rank_;
    explicit DSU(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int v) {                                    // сжатие путей
        return parent[v] == v ? v : parent[v] = find(parent[v]);
    }
    bool unite(int a, int b) {                           // объединение по рангу
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

Подсказки по коду:

• Конструктор помечен как explicit, чтобы случайно не сконвертировать int в DSU (например, при неявной передаче аргумента).
• Поле названо rank_ с подчёркиванием: rank — зарезервированное имя в Windows-заголовочниках, а в STL оно легко пересекается с другими идентификаторами.
• find реализован рекурсивно — коротко и читаемо. Для очень больших n (десятки миллионов) можно переписать итеративно, чтобы не уронить стек.
• unite возвращает false, если элементы уже в одном множестве — это удобно в алгоритме Краскала, чтобы пропускать лишние рёбра без дополнительной проверки наверху.

Применение:

• Алгоритм Краскала — DSU проверяет, не образует ли добавляемое ребро цикл: если unite вернул false, ребро пропускаем.
• Проверка связности графа — после серии unite два узла лежат в одной компоненте, если их find возвращает одно и то же значение.
• Динамические компоненты связности — когда в графе только добавляются рёбра, DSU отвечает на запросы «в одной ли компоненте a и b?» за почти O(1).
• Задача о друзьях и врагах — расширение DSU с дополнительной логикой: у каждого множества есть «цвет» (друг/враг), и правила объединения становятся нетривиальными.

Типичные ошибки:

• Забыть вызвать find внутри unite перед сравнением a == b — иначе сравниваются произвольные представители, и результат неверен.
• Использовать size вместо rank и обновлять его только у корня — нужно либо хранить size отдельно, либо аккуратно менять у выбранного корня.
• Думать, что DSU поддерживает удаление — это структура только для объединения, удаление элемента из множества не предусмотрено.
• На контестах забыть, что структуры struct могут быть запрещены: тогда выносят parent[] и rank[] в глобальные массивы, а find/unite — в свободные функции.

Сводная таблица структур данных. Ниже — сравнение сложностей основных операций. Сложности указаны для среднего (амортизированного) случая; в худшем случае поведение может быть хуже (хеш-таблица деградирует до O(n) при плохой хеш-функции и высокой нагрузке, а BST без балансировки — до O(n) на вырожденных вводах).

Сортировки

Сортировка — базовая задача: привести последовательность в порядок. Без неё не работают бинарный поиск, слияние баз данных, группировка в GROUP BY, некоторые этапы компрессии и почти любые алгоритмы, которые опираются на упорядоченные данные. Сортировка — это «фундамент», на котором строятся более сложные алгоритмы.

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

Сначала классификация: сортировки сравнением не могут быть быстрее O(n log n) в худшем случае (доказательство через дерево решений — любой алгоритм, принимающий решения через сравнения, можно представить как бинарное дерево, в котором n! листьев соответствуют разным перестановкам, а минимальная глубина такого дерева — log₂(n!) ≈ n log n), а сортировки без сравнения (подсчётом, поразрядная) обходят этот барьер за счёт знания о диапазоне ключей.

Почему это важно понимать: выбор между сравнительной и не сравнительной сортировкой определяется не «какая быстрее в среднем», а природой данных. Если ключи — целые числа в известном узком диапазоне, подсчёт/поразрядная могут оказаться на порядки быстрее. Если ключи — произвольные объекты с дорогим operator< и неизвестным диапазоном — выбираем из сравнительных.

Простые сортировки: вставками, выбором, пузырьком

Все три — O(n²) и служат для обучения. Зачем их вообще знать, если есть qsort/std::sort? Во-первых, на маленьких массивах (≈ n < 16–32) простые сортировки часто выигрывают у быстрых из-за низких накладных расходов — именно поэтому стандартные библиотеки используют их внутри гибридных алгоритмов (TimSort, Introsort). Во-вторых, они формируют интуицию для понимания сложных алгоритмов.

Сортировка вставками — аналогия: раскладываете карты в руке, по одной берёте новую и вставляете её в нужное место уже отсортированной части. Хороша на почти отсортированных данных (O(n) в лучшем случае — каждый элемент делает 0–1 сравнение и сразу встаёт на место) и стабильна (равные элементы не меняют порядок, потому что при a[j] > key мы сдвигаем строго большие, а равные остаются левее).

Сортировка выбором — аналогия: на прилавке лежат вперемешку товары; вы каждый раз ищете самый дешёвый и кладёте его в начало новой полки. Делает минимум перестановок (ровно n−1 swap), поэтому подходит, когда запись в массив дорогая (например, во flash-памяти или при записи в файл). Нестабильна в общем случае.

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

// Сортировка вставками: строим отсортированный префикс
void insertionSort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;                 // стабильна: строгое >
    }
}

// Сортировка выбором: минимум из хвоста — в начало
void selectionSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
        std::swap(a[i], a[min]);
    }
}

Типичные ошибки:

• В insertionSort написать a[j] >= key вместо >. Это сломает стабильность: равные элементы начнут переставляться, и относительный порядок одинаковых ключей изменится.
• В selectionSort инициализировать min = 0 вместо i и забыть про «уже отсортированный префикс» — лишние swap с самим собой, но всё равно корректно, хотя менее эффективно.
• Выйти за границы в цикле вставок: забыть j >= 0 в условии while — получите чтение a[-1].

Быстрая сортировка (Хоар)

Быстрая сортировка выбирает опорный элемент (pivot), разделяет массив так, что слева — элементы меньшие опоры, справа — большие (или равные), и рекурсивно сортирует получившиеся части. Это классическая стратегия «разделяй и властвуй».

Аналогия из жизни. Вы сортируете стопку книг по толщине. Берёте одну книгу как «эталон», ставите её на стол. Все тоньше — в левую стопку, все толще — в правую. Затем повторяете то же с каждой стопкой. Так работает partition.

Средняя сложность O(n log n), худшая O(n²) при неудачном выборе опоры (например, уже отсортированный массив и опора — первый элемент — каждый раз отделяет лишь один элемент). Рандомизация индекса опоры или выбор медианы из трёх убирают вырождение на практике.

Почему именно эта схема разбиения называется «Хоар» (а не «Ломуто»): в схеме Ломуто два указателя идут в одну сторону и разделяют массив на < pivot и ≥ pivot одним проходом — проще код, но хуже поведение на массивах с множеством равных элементов и при неудачном выборе опоры. Схема Хоара использует два указателя, идущих навстречу, — она быстрее и устойчивее к равным элементам, поэтому чаще используется в продакшен-коде.

// Разделение Хоара
int partition(int *a, int lo, int hi) {
    int pivot = a[(lo + hi) / 2];       // опора — середина
    int i = lo, j = hi;
    while (i <= j) {
        while (a[i] < pivot) i++;       // слева ищем >= pivot
        while (a[j] > pivot) j--;       // справа ищем <= pivot
        if (i <= j) { std::swap(a[i], a[j]); i++; j--; }
    }
    return i;                           // левая часть: [lo, i)
}

void quickSort(int *a, int lo, int hi) {
    if (lo >= hi) return;               // база: 0 или 1 элемент
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p, hi);
}

Быстрая сортировка нестабильна и требует O(log n) памяти на стек рекурсии в среднем, O(n) — в худшем случае. На практике это самая быстрая сортировка сравнением из-за хорошей локальности обращений к памяти (работает с соседними элементами массива, что дружелюбно к кэшу процессора) и малых констант.

Практические улучшения, которые применяют в реальных библиотеках:

1. Рандомизация опоры (std::swap(a[(lo+hi)/2], a[lo + rand() % (hi-lo+1))]) защищает от атаки «sorted input».
2. Медиана из трёх — выбираем опору как медиану из {a[lo], a[mid], a[hi]} — ещё лучше противостоит отсортированным входам.
3. Переход на insertion sort при малом размере подмассива (≈ 16 элементов): рекурсия прекращается раньше, и финальный проход insertionSort дешевле, чем углубляться дальше.
4. Introsort (используется в std::sort GCC/Clang): если глубина превысила 2·log₂(n), переключаемся на heapsort — гарантируем O(n log n) даже в худшем случае.
5. Оптимизация хвостовой рекурсии: рекурсивно вызываем сортировку для меньшей половины, а бо́льшую обрабатываем в цикле — это снижает глубину стека с O(log n) до O(log log n) в среднем.

Типичные ошибки:

• Использовать a[(lo + hi) / 2] без проверки на переполнение — для очень больших массивов lo + hi может выйти за INT_MAX. Безопаснее lo + (hi - lo) / 2.
• Возвращать j вместо i из partition и забыть, какая именно граница возвращается — путаница с quickSort(a, lo, p-1) vs quickSort(a, p, hi). Здесь p = i означает, что левый отрезок — [lo, i), правый — [i, hi).
• Забыть базу рекурсии if (lo >= hi) return; — бесконечная рекурсия и переполнение стека.

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

Сортировка слиянием делит массив пополам, рекурсивно сортирует половины и сливает (merge) их в один отсортированный отрезок. Это канонический пример стратегии «разделяй и властвуй».

Аналогия из жизни. У вас две стопки уже отсортированных карт. Вы кладёте их перед собой и берёте ту, у которой верхняя карта меньше. Так получаете одну общую отсортированную стопку. Именно так работает функция слияния.

Гарантированные O(n log n) в любом случае (лучшем, среднем, худшем), стабильность, но требует дополнительную память O(n) для буфера. Является основой внешней сортировки больших файлов, которые не помещаются в оперативную память (читаем чанками, сливаем).

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

void mergeSort(int *a, int *buf, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;       // безопасно от переполнения
    mergeSort(a, buf, lo, mid);
    mergeSort(a, buf, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= для стабильности
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    for (int t = lo; t < hi; t++) a[t] = buf[t];
}

Существует также bottom-up (итеративная) версия сортировки слиянием: проходим массив «окнами» длиной 1, 2, 4, 8, … и на каждом шаге сливаем соседние отрезки. Она не использует стек рекурсии (можно обойтись O(1) дополнительной памяти, если разрешено перезаписывать входной массив), что полезно в системах с жёсткими ограничениями по стеку.

Типичные ошибки:

• В условии слияния написать a[i] < a[j] вместо <= — это нарушит стабильность: при равенстве ключей из правой половины будут выбраны раньше, чем из левой, и относительный порядок изменится.
• Забыть циклы дозаливки остатков (while (i < mid) и while (j < hi)) — последние элементы просто потеряются.
• Копировать в буфер и обратно не весь массив, а только [lo, hi) — это правильно, но иногда по ошибке копируют [0, n) в каждом вызове, что даёт O(n log n) лишних копирований.

Пирамидальная сортировка (heapsort)

Сортировка работает в два этапа. Сначала строим max-кучу (двоичную кучу, в которой каждый родитель ≥ своих детей) за O(n), затем n раз меняем корень (максимум) с последним элементом и просеиваем кучу вниз, уменьшая её размер.

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

Почему построение кучи работает за O(n), а не за O(n log n)? Просеивание вниз на нижних уровнях дерева короткое (1–2 шага), а на верхних — длинное, но таких узлов мало. Математически сумма n/2·1 + n/4·2 + n/8·3 + … сходится к O(n). Это контринтуитивно, но проверено на практике.

Гарантированные O(n log n) и O(1) дополнительной памяти, но нестабильна и на практике медленнее быстрой из-за «прыжков» по памяти (родитель ↔ ребёнок — это индексы i, 2i+1, 2i+2, что плохо ложится в кэш процессора).

// Просеивание вниз в массиве a длиной n с корнем i
void siftDownRange(int *a, int n, int i) {
    while (true) {
        int l = 2 * i + 1, r = 2 * i + 2, largest = i;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heapSort(int *a, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) siftDownRange(a, n, i);   // построение кучи за O(n)
    for (int end = n - 1; end > 0; end--) {
        std::swap(a[0], a[end]);        // максимум — в конец
        siftDownRange(a, end, 0);       // восстановить кучу в [0, end)
    }
}

Практические заметки:

• Куча на массиве — это 0-индексированное дерево: корень в 0, левый ребёнок i — это 2i+1, правый — 2i+2, родитель — это (i-1)/2. Если в учебнике встретите 1-индексацию (2i, 2i+1, i/2) — это просто смещение формул на единицу.
• Heapsort — отличный выбор, когда нужна гарантия O(n log n) без дополнительной памяти: например, в ядре ОС или во встраиваемых системах, где аллокация запрещена.
• Min-кучу (где родитель ≤ детей) используют для приоритетных очередей, а для сортировки нужно именно max-куча — сортируем по убыванию, потом читаем с конца или меняем направление сравнения.

Типичные ошибки:

• Использовать 1-индексированные формулы для 0-индексированного массива (l = 2*i вместо 2*i+1) — массив будет «сломан», но ошибка проявится не сразу.
• Забыть, что после swap(a[0], a[end]) нужно просеивать только префикс [0, end), а не весь массив длины n — иначе мы будем «трогать» уже отсортированную часть и испортим порядок.
• Строить кучу «сверху вниз» через siftUp — будет O(n log n) вместо O(n), то есть правильно, но медленнее.

Сортировка подсчётом и поразрядная

Сортировка подсчётом (counting sort) работает за O(n + k), где k — диапазон значений: считаем частоты каждого ключа во вспомогательном массиве count, пересчитываем его в префиксные суммы (позиции, на которые должны попасть элементы), затем восстанавливаем порядок, проходя исходный массив с конца (это критично для стабильности).

Аналогия из жизни. У вас 1000 экзаменационных работ, и оценки от 1 до 5. Вы раскладываете их по 5 коробкам, потом берёте из коробок по одной и складываете в стопку — получаете отсортированный по оценкам набор. Это и есть counting sort.

Поразрядная (radix) сортировка применяется, когда ключи — числа или строки. Сортируем по разрядам от младшего к старшему (LSD-вариант) стабильной подсчётной сортировкой, давая O(d·(n + k)) для d разрядов и базы k (например, k = 256 для побайтовой обработки). Стабильность промежуточных сортировок гарантирует, что порядок, установленный на предыдущих разрядах, не нарушается при сортировке по следующим.

Почему LSD, а не MSD? LSD проще в реализации и использует стабильный counting sort «как есть», но требует, чтобы все ключи были одной длины (или обрабатывались как числа фиксированной разрядности с дополнением нулями). MSD экономит время на реально коротких ключах (например, многие строки различаются уже в первых символах), но требует более сложной рекурсии и аккуратного управления позициями.

// Сортировка подсчётом: подходит, когда значения в небольшом диапазоне [0, k]
void countingSort(int *a, int n, int k) {
    std::vector<int> count(k + 1, 0), out(n);
    for (int i = 0; i < n; i++) count[a[i]]++;
    for (int v = 1; v <= k; v++) count[v] += count[v - 1];   // префиксные суммы
    for (int i = n - 1; i >= 0; i--) out[--count[a[i]]] = a[i];  // с конца — стабильно
    for (int i = 0; i < n; i++) a[i] = out[i];
}

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

• Counting sort — когда диапазон k соизмерим с n или меньше, иначе массив count будет огромным. Например, сортировка оценок от 0 до 100, сортировка возрастов людей в опросе, ранжирование по частоте слов.
• Radix sort — когда ключи — длинные целые числа, UUID, IP-адреса, строки фиксированной длины. Это основа многих промышленных решений (например, сортировки строк в базах данных).

Типичные ошибки:

• Пройти по исходному массиву с начала при восстановлении — порядок равных элементов инвертируется, и стабильность ломается. Это самая частая ошибка в counting sort.
• Забыть, что массив count должен иметь размер k+1 для значений из [0, k] — выход за границы.
• Применить counting sort к массиву, где значения могут быть отрицательными или превышать k — нужно либо расширять диапазон (сдвиг на min), либо использовать другие алгоритмы. На практике проще нормализовать ключи заранее.
• Использовать int для count, когда в массиве много одинаковых значений — переполнение счётчика при n > 2³¹. Для надёжности лучше size_t или хотя бы проверять вход.

Сводная таблица сортировок

Сводная таблица помогает быстро подобрать алгоритм сортировки под конкретную задачу. Сложность указана для массива из n элементов; k — диапазон значений (для подсчёта и поразрядной), d — число разрядов. Память — дополнительная (стек рекурсии и/или вспомогательный буфер), не считая входного массива.

Что означают столбцы:

• Лучшая/Средняя/Худшая — количество операций в соответствующих сценариях. Нотация O большое скрывает константу: на практике разница между двумя O(n log n) алгоритмами может составлять разы, поэтому «средняя» оценка важнее «худшей» для реальных данных.
• Память — дополнительная память помимо входного массива: O(1) — на месте (in-place), O(log n) — только стек рекурсии, O(n) — вспомогательный буфер того же размера, что и массив.
• Стабильна — «Да» означает, что равные по ключу элементы сохраняют исходный взаимный порядок. Критично при многоуровневой сортировке: например, сначала по группе, затем по имени внутри группы — иначе порядок имён «потеряется».

Типичные ошибки при выборе:

• Брать быструю сортировку без случайного или медианного выбора опорного элемента — на уже отсортированных или специально подобранных данных она деградирует до O(n²) и может переполнить стек рекурсии на больших массивах.
• Использовать слияние там, где критична память (требуется буфер O(n)), или пирамидальную там, где нужна стабильность (структура кучи по своей природе её не даёт).
• Применять подсчёт при большом диапазоне k — массив счётчиков займёт огромную память и сортировка перестанет быть линейной по памяти, даже останется линейной по времени.
• Забывать, что вставки — лучший друг почти отсортированных данных (на них O(n)), а не просто «медленный алгоритм для обучения». Многие гибридные алгоритмы (Timsort в Python, Introsort в C++) используют вставки на маленьких подмассивах.
• Думать, что пузырьковая сортировка с флагом «уже отсортировано» — серьёзный алгоритм: на случайных данных она делает в ~4 раза больше обменов, чем вставки, и в ~100 раз больше, чем быстрая.

Поиск и строковые алгоритмы

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

Представьте себе словарь: если книги стоят на полках по алфавиту, вы не перебираете все книги подряд, а открываете примерно в середине и сразу понимаете, в какую сторону двигаться. Это и есть идея эффективного поиска.

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

Линейный, бинарный и тернарный поиск

Линейный поиск — самый простой алгоритм поиска. Мы перебираем все элементы один за другим, пока не найдём нужный. Время работы — O(n). Подходит для неотсортированных массивов и для маленьких наборов данных, где накладные расходы на сортировку не оправданы.

Бинарный поиск — алгоритм поиска в отсортированном массиве. На каждом шаге берём средний элемент и сравниваем его с искомым: если он меньше — ищем в правой половине, иначе — в левой. Это отсекает половину оставшихся элементов за один шаг, поэтому время работы — O(log n).

Аналогия из жизни. Бинарный поиск — это игра «Угадай число от 1 до 100»: вы спрашиваете «больше или меньше 50?», потом «больше или меньше 75?» и так далее. Каждый вопрос вдвое сокращает диапазон, и за ~7 вопросов вы гарантированно угадаете.

Тернарный поиск — ищет минимум или максимум унимодальной функции (функции, которая сначала убывает, потом возрастает, или наоборот — имеет один «изгиб»). На каждом шаге интервал делится на три части с помощью двух пробных точек, и одна из частей отбрасывается. Время работы — O(log n), но константа больше, чем у бинарного.

Главные ловушки бинарного поиска — неверная граница и переполнение mid.

Типичные ошибки:

1. Переполнение при вычислении mid. Прямое (lo + hi) / 2 ломается на больших значениях (когда lo + hi превышает INT_MAX, а это возможно уже при размере массива в 2³¹). Всегда пишите lo + (hi - lo) / 2 — это безопасно.
2. Неверный выбор границ. Путаница между [lo, hi], [lo, hi) и (lo, hi) — главный источник ошибок в бинарном поиске. Согласуйте инвариант («что истинно на каждой итерации») и пишите код строго по нему, иначе можно потерять граничный элемент или зациклиться.
3. Забытый случай равенства. Иногда нужна первая позиция элемента, иногда — последняя. Это даёт разные версии: lower_bound (первый >= x) и upper_bound (первый > x). Смешивание — частая причина ошибок «на единицу».
4. Бинарный поиск по неотсортированному массиву. Если данные не упорядочены, алгоритм молча выдаёт мусор. Всегда проверяйте предусловие.

// Первый индекс, где a[i] >= x; n — длина
int lowerBound(const int *a, int n, int x) {
    int lo = 0, hi = n;                 // полуинтервал [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // НЕ (lo + hi) / 2 — иначе переполнение
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Хеш строк (полиномиальный)

Полиномиальный хеш — способ превратить строку в число так, чтобы разные строки с высокой вероятностью давали разные числа. Идея: каждый символ — это «цифра» в системе счисления с основанием p, а вся строка — одно большое число, взятое по модулю m.

Строку можно представить числом: h = s[0]·p^(L−1) + s[1]·p^(L−2) + … + s[L−1] по модулю m. По сути мы трактуем строку как число в системе счисления с основанием p и берём остаток от деления на m.

Зачем это нужно? Тогда сравнение строк — это сравнение чисел (одна операция), а подстроки сравниваются за O(1) через префиксные хеши (без посимвольного прохода по символам).

Префиксные хеши — массив, где h[i] — это хеш первых i символов строки. Имея такой массив и массив степеней p^k mod m, можно получить хеш любой подстроки [l, r) за O(1) по формуле: hash(l, r) = (h[r] − h[l] · p^(r−l)) mod m.

Аналогия из жизни. Хеш — это как «отпечаток пальца» строки: одинаковые строки дают одинаковый отпечаток, разные — почти наверняка разный. Это позволяет сравнивать длинные тексты мгновенно, не читая их целиком.

Типичные ошибки:

1. Отрицательные значения при вычитании по модулю. В C++ остаток от деления отрицательного числа — отрицательный. Всегда добавляйте m: ((x % m) + m) % m. Иначе хеши будут «отрицательными», и сравнения сломаются.
2. Маленькое основание p (например, 2 или 10) часто приводит к коллизиям. Используйте простое число > размера алфавита (например, 257 для ASCII, 91138233 для широкого алфавита). Большое основание уменьшает корреляции между позициями символов.
3. Одинарный модуль — уязвим к специально подобранным коллизиям (когда злоумышленник знает ваш M). В олимпиадных задачах обычно достаточно одного модуля, в продакшене и при строковых задачах на большие тексты используют двойной хеш (два разных модуля, сравнивают обе пары) — это снижает вероятность коллизии до практически нулевой.
4. Забыть про unsigned char. Если приводить char напрямую к числу, отрицательные char (для кодов > 127) дадут неверные значения. Всегда приводите к unsigned char перед подстановкой в формулу.

Полиномиальный хеш — основа Рабина–Карпа и многих задач на подстроки.

// Префиксные хеши: h[i] = хеш префикса длины i
const long long P = 257, M = 1000000007;

std::vector<long long> buildHashes(const std::string &s) {
    std::vector<long long> h(s.size() + 1, 0);
    for (size_t i = 0; i < s.size(); i++)
        h[i + 1] = (h[i] * P + (unsigned char)s[i]) % M;
    return h;
}

// Хеш подстроки [l, r) = (h[r] - h[l] * P^(r-l)) mod M
long long subHash(const std::vector<long long> &h,
                  const std::vector<long long> &powP, int l, int r) {
    return ((h[r] - h[l] * powP[r - l]) % M + M) % M;
}

Алгоритм Рабина–Карпа

Рабин–Карп — алгоритм поиска подстроки, основанный на хешировании. Идея: вместо того чтобы посимвольно сравнивать образец с каждым окном текста, мы сначала сравниваем их хеши (числа), и только при совпадении хешей выполняем дорогостоящую посимвольную проверку. Это позволяет «отсеивать» большинство окон за одну операцию сравнения чисел.

Алгоритм ищет образец длины m в тексте за O(n + m) в среднем: считает хеш образца и хеши всех окон текста, сравнивая числа. При совпадении хешей проверяет строки посимвольно, чтобы исключить коллизии.

Аналогия из жизни. Представьте, что вы ищете конкретную книгу в стопке. Вместо того чтобы открывать каждую и читать, вы сначала смотрите на корешок — там стоит «отпечаток» (хеш, например, штрих-код). Если штрих-коды совпали — открываете и проверяете, та ли это книга. Большинство книг вы отбросите по штрих-коду за секунду.

Среднее O(n + m) достигается за счёт трюка со «скользящим хешем»: хеш следующего окна текста вычисляется из хеша предыдущего за O(1) по формуле — мы убираем вклад ушедшего символа и добавляем вклад нового. Без этого трюка было бы O(n·m), потому что хеш каждого окна пришлось бы считать заново.

Худшее время — O(n·m), если коллизии происходят на каждом шаге (например, при специально подобранных входных данных). На практике и в олимпиадных задачах это маловероятно.

Типичные ошибки:

1. Сравнение хеша без посимвольной проверки. Хеши могут совпадать у разных строк (коллизия). Всегда проверяйте строку при совпадении хешей через text.compare(i, m, pat) == 0, иначе алгоритм выдаст ложные срабатывания.
2. Переполнение при скользящем хеше. При вычитании text[i] * pPow нужно приводить к long long и брать ((th % M) + M) % M, чтобы избежать отрицательных значений после умножения и вычитания.
3. Не учтена граница if (i + m < n). На последнем окне не нужно пересчитывать хеш — мы уже сравнили всё, что можно. Без этой проверки алгоритм либо выйдет за границу, либо сделает лишнюю операцию с мусорным значением.
4. Забыть про пустой образец. Если образец пустой, его длина m = 0, и pPow останется 1. Алгоритм должен либо явно обработать этот случай, либо вернуть пустой результат (по соглашению).

std::vector<int> rabinKarp(const std::string &text, const std::string &pat) {
    const long long P = 257, M = 1000000007;
    int n = (int)text.size(), m = (int)pat.size();
    if (m > n) return {};
    long long ph = 0, th = 0, pPow = 1;
    for (int i = 0; i < m; i++) {
        ph = (ph * P + (unsigned char)pat[i]) % M;
        th = (th * P + (unsigned char)text[i]) % M;
        if (i < m - 1) pPow = pPow * P % M;    // P^(m-1)
    }
    std::vector<int> res;
    for (int i = 0; i + m <= n; i++) {
        if (ph == th && text.compare(i, m, pat) == 0) res.push_back(i);  // проверка от коллизий
        if (i + m < n)
            th = ((th - (unsigned char)text[i] * pPow) * P + (unsigned char)text[i + m]) % M;
        th = (th + M) % M;
    }
    return res;
}

Алгоритм Кнута–Морриса–Пратта (КМП)

КМП — алгоритм поиска подстроки, который никогда не возвращается назад по тексту. Главный герой — префикс-функция.

Префикс-функция pi[i] — длина наибольшего собственного префикса строки s[0..i], который одновременно является её суффиксом. То есть мы ищем самую длинную подстроку, которая «обёрнута» вокруг позиции i и с двух сторон совпадает с самой собой. Например, для строки «абаба» pi[4] = 3, потому что «аба» — это и префикс, и суффикс.

КМП ищет образец за O(n + m), не возвращаясь по тексту назад. Ключ — префикс-функция: pi[i] равно длине наибольшего собственного префикса строки s[0..i], который совпадает с её суффиксом. При несовпадении образец сдвигается по pi, а не на единицу.

Аналогия из жизни. Представьте, что вы ищете слово «мама» в тексте «мам…ама…мама». Когда вы прочли «мам» и следующая буква не совпала, вы не начинаете заново с «м», а помните: «у нас уже совпал префикс ‘ма’», — и продолжаете с этого места. Префикс-функция — это и есть такая «память» о том, сколько символов образца уже совпало и куда безопасно откатиться без потери информации.

Почему O(n + m)? Каждый символ текста обрабатывается ровно один раз, причём указатель j (длина совпавшего префикса) либо растёт, либо откатывается по уже вычисленным pi. Суммарное число уменьшений j не превышает числа увеличений, поэтому общая работа линейна — никакого наивного O(n·m).

Типичные ошибки:

1. Перепутать индекс при нахождении вхождения. Когда pi[i] == m (длина образца), это означает: образец только что нашёлся, оканчиваясь в позиции i в склеенной строке pat + '#' + text. Нужно аккуратно посчитать индекс начала вхождения в исходном тексте: i - 2*m для стандартного склеивания (вычитаем длину образца дважды — один раз из-за #, другой — из-за самого образца).
2. Символ-разделитель. При поиске вхождений образца в текст склеивают pat + '#' + text, где # — символ, заведомо не встречающийся ни в образце, ни в тексте. Иначе префикс-функция «протечёт» через границу и выдаст ложные срабатывания (например, найдёт вхождение, начинающееся внутри образца).
3. Откат в while (j > 0 && s[i] != s[j]) j = pi[j-1]; — это критичная строка. Нельзя ставить j = 0 вместо цикла: тогда мы теряем информацию о частичных совпадениях и получаем наивный поиск O(n·m). Цикл рекурсивно «сжимает» совпавший префикс до тех пор, пока не найдётся либо совпадение, либо пустой префикс.
4. Длина образца больше длины текста. Без проверки if (m > n) return {}; (или аналогичной) алгоритм может зациклиться или выдать мусор.

// Префикс-функция: pi[i] — длина наибольшего префикса-суффикса
std::vector<int> prefixFunction(const std::string &s) {
    std::vector<int> pi(s.size(), 0);
    for (size_t i = 1; i < s.size(); i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // откат по границе
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// Все вхождения pat в text: клеим pat + '#' + text
std::vector<int> kmp(const std::string &text, const std::string &pat) {
    std::string s = pat + "#" + text;
    std::vector<int> pi = prefixFunction(s), res;
    for (size_t i = pat.size() + 1; i < s.size(); i++)
        if (pi[i] == (int)pat.size()) res.push_back((int)i - 2 * (int)pat.size());
    return res;
}

Z-функция

Z-функция — массив z[i], где z[i] равно длине наибольшего общего префикса строки s и её суффикса, начинающегося в позиции i. Проще говоря, сколько символов подряд, начиная с s[i], совпадают с началом строки s. По соглашению z[0] = n (строка совпадает сама с собой целиком), хотя в приведённом коде z[0] остаётся 0 — обе версии встречаются и обе корректны, если вы последовательны.

z[i] равно длине наибольшего общего префикса строки s и её суффикса, начинающегося в i. Z-функция вычисляется за O(n) с использованием уже найденного отрезка [l, r] и решает те же задачи, что и префикс-функция (поиск подстроки, период строки).

Аналогия из жизни. Представьте, что вы прикладываете две ленты к строке: одна неподвижная (с начала s), вторая движется вдоль строки, начиная с позиции i. z[i] — сколько символов они совпадают, прежде чем встретят первое различие. Если вы помните самый правый участок, где ленты ещё шли вровень ([l, r]), для следующих позиций можно не сравнивать заново посимвольно, а взять готовый ответ и продолжить лишь с того места, где ленты точно «расходятся».

Отрезок [l, r] — это «лучшее окно совпадения», найденное к текущему моменту: самая правая позиция, до которой строки s и s[l..] ещё совпадают. Если новая позиция i попадает внутрь [l, r], мы сразу знаем, что z[i] >= min(r − i, z[i − l]) — и не пересчитываем заново. Это и даёт линейное время: каждый символ либо попадает в уже известное окно, либо сравнивается заново, но правый край r при этом только растёт.

Связь с префикс-функцией. Z-функция и префикс-функция решают одни и те же задачи (поиск подстроки, поиск периода строки, количество различных подстрок и др.). Выбор между ними — дело вкуса: Z-функцию обычно проще понять интуитивно (наглядная «геометрия» отрезка [l, r]), префикс-функция чуть компактнее по коду. Одну легко пересчитать через другую за линейное время.

Типичные ошибки:

1. Не поддерживать [l, r]. Без этого отрезка алгоритм вырождается в наивное посимвольное сравнение каждой позиции с началом — O(n²). Это самая частая ошибка при реализации «по памяти».
2. Граница z[i] = std::min(r - i, z[i - l]). Нельзя ставить просто z[i - l] — за границей [l, r] совпадение может оборваться, и тогда z[i − l] будет завышен (мы скопируем ответ, который относится к более короткому совпадению).
3. Сравнение s[z[i]] == s[i + z[i]] без проверки i + z[i] < n. Если забыть про границу массива, при z[i], доходящем до конца строки, получим выход за пределы и неопределённое поведение.
4. Склеивание строк для поиска подстроки. Чтобы найти все вхождения pat в text, склеивают pat + '$' + text и ищут позиции, где z[i] == m. Здесь $ — символ-разделитель, как и в КМП, чтобы окно не «протекало» через границу.

std::vector<int> zFunction(const std::string &s) {
    int n = (int)s.size();
    std::vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = std::min(r - i, z[i - l]);       // используем найденный отрезок
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

Алгоритм Бойера–Мура (обзор)

Что это (простое определение): Бойер–Мур — алгоритм поиска подстроки (образца) в тексте. Считается одним из самых быстрых на практике. Главная идея — сравнение идёт справа налево внутри окна, а при несовпадении окно сдвигается сразу на несколько позиций по двум таблицам эвристик: «плохого символа» и «хорошего суффикса».

Аналогия из жизни: обычный алгоритм действует как невнимательный читатель — смотрит первую букву образца, потом вторую, и т. д. Бойер–Мур — как опытный читатель: смотрит на последнюю букву образца и, если в тексте в этой позиции стоит, скажем, «Ы», сразу понимает, что здесь слово «КОРОВА» начаться не может (в образце нет «Ы»), и прыгает через несколько букв сразу.

Как работают сдвиги (идея):

1. Образец выравнивается по началу текста (окно = длина образца m).
2. Сравнение символов идёт справа налево внутри окна.
3. При первом несовпадении вычисляется сдвиг по двум эвристикам:
   • Эвристика плохого символа (bad character): сдвинуть образец так, чтобы символ текста, который не совпал, встал под ближайшее справа вхождение этого же символа в образце; если такого символа в образце нет — сдвинуть за весь образец.
   • Эвристика хорошего суффикса (good suffix): если часть суффикса образца уже совпала с текстом, сдвинуть образец так, чтобы этот суффикс наложился на другое подходящее место в образце (или вышел за его пределы).
4. Из двух сдвигов берётся максимальный (безопаснее сдвинуть дальше, чем меньше — иначе можно пропустить вхождение).
5. Предобработка образца строит обе таблицы за O(m + σ), где σ — размер алфавита.

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

Практические подсказки:

• В реальных задачах (утилита grep, strstr в glibc, поиск в редакторах) используют именно Бойера–Мура или его упрощения — алгоритмы Horspool и Sunday.
• На экзамене достаточно: знать идею двух эвристик, что предобработка образца даёт таблицы, и что средняя практическая скорость суб-линейная.
• Если нужна только эвристика плохого символа — это сильно проще в реализации, алгоритм всё равно будет корректным, просто иногда медленнее в худших случаях.
• Эвристика хорошего суффикса сложнее, но даёт лучшие гарантии сдвига; именно она выводит сложность до O(n+m) при аккуратной реализации.

Типичные ошибки:

• Путать, какая эвристика какую таблицу строит: плохой символ → таблица по символам алфавита, хороший суффикс → таблица по длинам суффиксов.
• Считать Бойера–Мура «всегда O(n+m)». Это верно для аккуратных реализаций с Z-функцией, наивная версия в худшем случае O(n·m) (например, текст из одинаковых букв aaaa… и образец aab).
• Забыть, что сдвиги должны быть максимальными из двух, иначе можно перепрыгнуть через вхождение.

Фильтр Блума

Что это (простое определение): Фильтр Блума — вероятностная структура данных для проверки принадлежности элемента множеству. В отличие от хеш-сета, она не хранит сами элементы, а только их «отпечатки» в битовом массиве. Ответ «элемента точно нет» — всегда верен; «элемент возможно есть» — может ошибаться (это называется ложное срабатывание, false positive).

Аналогия из жизни: представьте библиотеку с миллионами книг. Хранить весь каталог названий — огромная память. Вместо этого повесьте доску с тысячами флажков (битовый массив). Когда книга добавляется, по её названию вычисляются, например, 3 номера флажков, и эти флажки поднимаются. Запрос: если все 3 флажка подняты — «возможно есть»; если хоть один опущен — «точно нет». Разные книги могут случайно поднять одни и те же флажки — отсюда и ложные срабатывания.

Как устроен (пошагово):

1. Битовый массив длины M, все биты инициализированы нулём.
2. k независимых хеш-функций h₁, …, hₖ (на практике часто эмулируют через одну хеш-функцию + линейные комбинации, как в коде ниже).
3. Добавление add(x): для каждой hᵢ вычислить индекс 0 … M-1 и установить бит в 1.
4. Проверка maybeContains(x): вычислить те же k индексов; если все биты в этих позициях равны 1 — вернуть true («возможно есть»), если хотя бы один 0 — вернуть false («точно нет»).

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

О сложности и гарантиях:

• Время: O(k) на добавление и проверку, k обычно фиксировано (3–10).
• Память: O(M) бит — в разы меньше, чем хранение множества.
• Гарантия: приближённая. Ложных пропусков нет (существующий элемент всегда даст true), но ложные срабатывания возможны — их вероятность настраивается выбором M и k.
• Удаление в классическом фильтре Блума не поддерживается — для этого используют Counting Bloom Filter.

Где применяют: кэши и proxy (проверка, есть ли URL в blacklist'е), антиспам-фильтры, базы данных (Cassandra, HBase, RocksDB), ускорение чтения «диск/Cache», дедупликация.

Практические подсказки:

• В показанной реализации трюк: одна хеш-функция + линейные комбинации h1 + i·h2 эмулируют k хешей за один проход по строке.
• M = 1 << 20 — это ~1 Мбит ≈ 128 КБ памяти, удобно влезает в L2-кэш процессора.
• Чем больше элементов добавлено, тем выше вероятность false positive — фильтр нужно периодически перестраивать или масштабировать.
• В продакшене лучше брать готовую реализацию (Boost.Containers, профильные библиотеки), а не писать свою.

Типичные ошибки:

• Думать, что фильтр Блума отвечает «точно есть» — нет, только «возможно есть».
• Использовать k = 1. Это вырождается в обычный хеш-сет и теряется весь смысл фильтра Блума.
• Пытаться удалить элемент «сбросом бита» — нельзя, этот же бит мог быть выставлен другим элементом.
• Путать ложное срабатывание и пропуск: фильтр никогда не пропускает существующий элемент, но может ошибочно «найти» отсутствующий.

#include <bitset>

class BloomFilter {
    static const int M = 1 << 20;       // число бит
    std::bitset<M> bits;
public:
    void add(const std::string &s) {
        size_t h1 = std::hash<std::string>{}(s);
        size_t h2 = std::hash<size_t>{}(h1);
        bits[h1 % M] = true;
        bits[(h1 + h2) % M] = true;
        bits[(h1 + 2 * h2) % M] = true; // три хеша
    }
    bool maybeContains(const std::string &s) const {
        size_t h1 = std::hash<std::string>{}(s);
        size_t h2 = std::hash<size_t>{}(h1);
        return bits[h1 % M] && bits[(h1 + h2) % M] && bits[(h1 + 2 * h2) % M];
    }
};

Графы

Граф — это математическая структура G = (V, E), где V — множество вершин (узлов, точек), а E — множество рёбер (связей между ними). Простыми словами: вершины — это объекты, а рёбра — отношения между ними.

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

Рёбра бывают:

• направленные (орграф, directed graph) — например, A → B означает «можно пройти от A к B, но не обратно» (как улица с односторонним движением);
• ненаправленные — проезд в обе стороны (как обычная двусторонняя дорога);
• взвешенные — с числовым значением (длина, стоимость, время);
• невзвешенные — все рёбра «равны».

Почти все графовые задачи сводятся к одной из четырёх больших тем: обход (посетить все вершины), кратчайшие пути (найти минимум расстояния), остовные деревья (соединить вершины минимальной суммой рёбер) или потоки (пропускная способность сети). Освоив эти четыре кита, вы решите 90% практических задач на графах.

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

Способ хранения графа в памяти определяет, сколько памяти он съест и какие операции будут быстрыми. Три классических представления различаются именно этим компромиссом между памятью и скоростью проверки ребра.

Почему такие оценки:

• Матрица смежности — двумерный массив adj[V][V], где adj[u][v] = true, если есть ребро. Память квадратичная, потому что храним клетку для каждой пары вершин (даже если ребра нет), зато проверка ребра — мгновенное обращение к массиву.
• Список смежности — для каждой вершины храним только её реальных соседей. Памяти тратится ровно столько, сколько рёбер, поэтому для разреженных графов это в разы экономичнее матрицы.
• Список рёбер — массив пар (u, v), без какой-либо индексации по вершинам. Памяти минимум, но любая проверка требует просмотра всего списка.

Когда что выбирать (практические подсказки):

• Матрица смежности — для плотных графов, где рёбер почти V² (например, граф друзей в маленьком коллективе). Тогда матрица не «раздута» и даёт мгновенную проверку ребра.
• Список смежности — для разреженных графов (типичный случай: социальные сети, карты дорог, веб-графы). Реальные графы почти всегда разреженные, поэтому в 95% задач используют именно его.
• Список рёбер — удобен для алгоритма Краскала (построение минимального остова), которому рёбра нужны в порядке возрастания веса; быстрая сортировка массива рёбер куда удобнее, чем обходить списки смежности.

Аналогия из жизни: матрица смежности — это таблица «кто с кем знаком» на весь класс, заполненная галочками (много пустых клеток). Список смежности — это контактная книга телефона: у каждого человека записаны только реальные друзья. Список рёбер — это просто стопка бумажек «Маша — Вася, Петя — Коля», без какой-либо структуры.

// Список смежности: вектор векторов
std::vector<std::vector<int>> g(n);        // g[v] — соседи v
g[u].push_back(v);
g[v].push_back(u);                          // для неориентированного

// Взвешенный список смежности: пары (сосед, вес)
std::vector<std::vector<std::pair<int,int>>> wg(n);
wg[u].push_back({v, w});

Обход в глубину (DFS)

DFS (Depth-First Search) — обход, который идёт как можно глубже по одной ветви, пока есть непосещённые соседи, затем откатывается назад (backtracking) и пробует следующего соседа.

Аналогия из жизни: вы в лабиринте. Идёте прямо до упора, пока не упрётесь в тупик или уже посещённую комнату. Тогда возвращаетесь на последнюю развилку и поворачиваете в другую сторону. Так работает исследование пещеры спелеологом или поиск выхода в игре.

Почему именно так: рекурсия естественно моделирует «откат» — стек вызовов хранит, куда возвращаться. Каждая вершина обрабатывается ровно один раз, каждое ребро — максимум два раза (в неориентированном графе), отсюда сложность O(V + E).

Рекурсивный вариант прост и читаем, но при очень глубоком графе (например, цепочка из 10⁵ вершин) можно получить переполнение стека. Тогда используют итеративный вариант со своим стеком (std::stack<int>).

Типичная ошибка №1: забыть массив visited — гарантированная бесконечная рекурсия (или бесконечный цикл) при первом же цикле в графе. Типичная ошибка №2: пометить вершину после обработки соседей, а не до. Тогда вы зайдёте в одну вершину из двух разных веток и сделаете двойную работу (или опять зациклитесь).

void dfs(int v, const std::vector<std::vector<int>> &g, std::vector<bool> &visited) {
    visited[v] = true;                      // помечаем ДО обхода соседей
    for (int to : g[v])
        if (!visited[to]) dfs(to, g, visited);
}

Обход в ширину (BFS)

BFS (Breadth-First Search) — обход волнами: сначала посещаем всех соседей стартовой вершины (расстояние 1), потом их соседей (расстояние 2), потом соседей соседей (расстояние 3) и так далее.

Аналогия из жизни: бросьте камень в воду — от точки падения расходятся круговые волны. Каждая следующая волна — это вершины на расстоянии k+1 от центра. Или представьте слух в маленьком городке: за день все знакомые узнали новость (1 шаг), на следующий день — их знакомые (2 шага), и так далее.

Почему BFS даёт кратчайшие пути: на невзвешенном графе впервые попасть в вершину v можно только кратчайшим путём — ведь мы обходим уровень за уровнем, и до того, как очередь дойдёт до более дальних путей, мы уже зафиксируем dist[v]. Отсюда сложность O(V + E).

Почему очередь обязательна: BFS требует именно FIFO (первым вошёл — первым вышел), чтобы обрабатывать вершины в порядке возрастания расстояния. Если случайно использовать std::stack, получится DFS, а не BFS.

Практическая подсказка: массив dist сразу служит и признаком посещения (-1 означает «не посещали»). Это экономит память и упрощает код по сравнению с отдельным visited.

Типичная ошибка: проверять if (!visited[to]) и при этом забыть dist[to] = dist[v] + 1 — получите BFS, который не считает расстояния.

std::vector<int> bfs(int s, const std::vector<std::vector<int>> &g) {
    std::vector<int> dist(g.size(), -1);
    std::queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : g[v])
            if (dist[to] == -1) {          // ещё не посещена
                dist[to] = dist[v] + 1;
                q.push(to);
            }
    }
    return dist;
}

Компоненты связности

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

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

Как найти: запускаем DFS/BFS из каждой ещё не посещённой вершины. Каждый запуск обходит ровно одну компоненту, поэтому число запусков равно числу компонент. Все вершины, посещённые за один запуск, принадлежат одной компоненте.

Почему это работает: DFS из вершины v по определению доходит до всех вершин, до которых есть путь из v. Это и есть компонента связности.

Практическое применение: определение изолированных групп пользователей в соцсети, проверка связности компьютерной сети, разбиение графа на независимые подзадачи.

int components(const std::vector<std::vector<int>> &g) {
    std::vector<bool> visited(g.size(), false);
    int count = 0;
    for (int v = 0; v < (int)g.size(); v++)
        if (!visited[v]) { dfs(v, g, visited); count++; }
    return count;
}

Топологическая сортировка

Топологическая сортировка упорядочивает вершины орграфа без циклов (DAG — Directed Acyclic Graph) так, что для каждого ребра u → v вершина u идёт в итоговом порядке раньше v. Это линейное упорядочение, согласованное со всеми направленными рёбрами.

Аналогия из жизни: расписание учебного плана. Курс «Алгоритмы» требует курс «Программирование», а «Программирование» — школьную информатику. Топологическая сортировка выстроит порядок: сначала информатика, потом программирование, потом алгоритмы. Или сборка детали на конвейере: нельзя ставить колёса до того, как собрана рама.

Алгоритм Кана (Kahn): работает с входящей степенью (indeg[v] — число рёбер, входящих в v).

1. Кладём в очередь все вершины с indeg == 0 (у них нет неудовлетворённых зависимостей — их можно «выполнить» первыми).
2. Достаём вершину из очереди, добавляем в ответ, для всех её исходящих соседей уменьшаем indeg на 1 (логически «удаляем» ребро).
3. Если у соседа indeg стал 0 — он готов, кладём в очередь.
4. Если обработали меньше V вершин — в графе есть цикл, и топсорта не существует.

Почему это работает: в DAG всегда есть хотя бы одна вершина с indeg == 0 (иначе был бы цикл). Удаляя такие вершины, мы шаг за шагом «разматываем» граф.

Типичная ошибка: забыть уменьшать indeg для всех соседей — получится бессмысленная последовательность, либо вечный цикл.

std::vector<int> topoSort(int n, const std::vector<std::vector<int>> &g) {
    std::vector<int> indeg(n, 0), order;
    for (int v = 0; v < n; v++)
        for (int to : g[v]) indeg[to]++;
    std::queue<int> q;
    for (int v = 0; v < n; v++)
        if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        order.push_back(v);
        for (int to : g[v])
            if (--indeg[to] == 0) q.push(to);
    }
    return order;                           // order.size() < n — есть цикл
}

Проверка двудольности и поиск циклов

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

Аналогия из жизни: расписание футбольного чемпионата. Каждую игру можно рассматривать как ребро между двумя командами. Хотим разбить команды на две группы так, чтобы в каждом матче встречались команды из разных групп — тогда все матчи «честно» пересекают границу. Если такое разбиение существует — граф двудольный.

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

Алгоритм проверки: BFS/DFS с раскраской. Стартуем из вершины, красим её в цвет 0. Каждого соседа красим в противоположный цвет (color ^ 1). Если встретили соседа, уже окрашенного в тот же цвет — конфликт, граф не двудольный.

Поиск циклов — два разных алгоритма:

• В неориентированном графе: при DFS запоминаем родителя (parent). Ребро к вершине считается «назад к предку», только если это не ребро к родителю. Если встретили уже посещённую вершину, не являющуюся родителем — нашли цикл.
• В ориентированном графе: используется трёхцветная раскраска (белый = не посещали, серый = в стеке рекурсии, чёрный = обработан полностью). Цикл есть, если из серой вершины есть ребро в серую (это и есть «обратное» ребро в DFS-дереве). Эта техника мощнее и работает в обеих задачах одновременно.

Типичная ошибка: проверять только color[to] != color[v], но не различать «ещё не окрашен» и «уже противоположный цвет». Нужна именно проверка на равенство с текущим цветом, как показано в коде.

// Двудольность: -1 — не окрачена, 0/1 — цвета
bool isBipartite(const std::vector<std::vector<int>> &g) {
    std::vector<int> color(g.size(), -1);
    for (int s = 0; s < (int)g.size(); s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        std::queue<int> q; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int to : g[v]) {
                if (color[to] == -1) { color[to] = color[v] ^ 1; q.push(to); }
                else if (color[to] == color[v]) return false;   // конфликт
            }
        }
    }
    return true;
}

Мосты и точки сочленения

Мост — это ребро графа, при удалении которого граф распадается на большее число компонент связности, чем было. Точка сочленения (articulation point) — это вершина с тем же свойством: убери её — и связный граф «рассыпается» на части. Простой пример из жизни: мост через реку — если его убрать, два берега перестают быть связаны.

Алгоритм Тарьяна находит их за один проход DFS, используя два массива:

• tin[v] — время входа в вершину v (как будто DFS пронумеровал вершины в порядке обнаружения);
• low[v] — минимальное время входа, достижимое из поддерева v не более чем через одно обратное ребро (то есть не поднимаясь дальше предка).

Почему low[to] > tin[v] означает мост? Из поддерева to нет ни одного обратного ребра, ведущего в v или выше, — значит, ребро (v, to) — единственный «канат», связывающий поддерево с остальной частью графа. Удали его — и часть отвалится.

std::vector<int> tin, low;
std::vector<bool> isBridge;
int timer = 0;

void bridgeDfs(int v, int parent, const std::vector<std::vector<std::pair<int,int>>> &g) {
    tin[v] = low[v] = timer++;
    for (auto [to, id] : g[v]) {
        if (id != parent) {                 // id ребра, а не вершина — кратные рёбра
            if (tin[to] != -1) low[v] = std::min(low[v], tin[to]);
            else {
                bridgeDfs(to, id, g);
                low[v] = std::min(low[v], low[to]);
                if (low[to] > tin[v]) isBridge[id] = true;   // мост
            }
        }
    }
}

Практические подсказки:

• Изначально tin заполняйте значением -1 — это маркер «вершина ещё не посещена». low зачастую инициализируется параллельно в DFS, отдельная инициализация не нужна.
• В parent передаётся id ребра, а не вершина-родитель: это защита от ситуации, когда в графе есть кратные рёбра (parallel edges) между двумя вершинами — иначе мы ошибочно решим, что идём по ребру обратно в предка.
• Тот же код легко превратить в поиск точек сочленения: после рекурсивного вызова проверяйте low[to] >= tin[v] (а не строгое >) и отдельно обрабатывайте корень DFS (у которого должно быть как минимум два таких ребёнка).
• Типичная ошибка: забыть, что timer нужно увеличивать до или после присваивания, но обязательно согласованно с проверкой tin[to] != -1. Случайный повторный заход в одну и ту же вершину испортит весь алгоритм.

Алгоритм Дейкстры

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

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

std::vector<long long> dijkstra(int s, const std::vector<std::vector<std::pair<int,int>>> &g) {
    const long long INF = 4e18;
    std::vector<long long> dist(g.size(), INF);
    using P = std::pair<long long,int>;                 // (расстояние, вершина)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (d != dist[v]) continue;                     // устаревшая запись — пропускаем
        for (auto [to, w] : g[v])
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                pq.push({dist[to], to});
            }
    }
    return dist;
}

Практические подсказки:

• INF берётся большим (здесь 4e18), чтобы при сложении dist[v] + w не случилось переполнения long long. Универсальное правило: INF + что-то < INF всё ещё должно быть ложью.
• Проверка if (d != dist[v]) continue; отбрасывает устаревшие записи — мы могли положить в очередь несколько оценок одной вершины, и актуальна только последняя.
• Сложность O((V + E) log V) достигается благодаря priority_queue. Если граф плотный (E ≈ V²) и веса небольшие, часто выгоднее O(V²) вариант без кучи — на практике он быстрее из-за меньших констант.
• Типичная ошибка: пытаться использовать Дейкстру при наличии отрицательных рёбер. Контрпример: граф s → a (вес 1), s → b (вес 0), b → a (вес -2) — оптимальный путь s → b → a имеет длину -2, но жадный выбор обработает a раньше с расстоянием 1 и зафиксирует его. Для отрицательных весов нужен Беллман–Форд.
• Для очень больших графов (V, E в миллионах) применяют Дейкстру на deque (0-1 BFS не подходит, но есть вариант с «radix heap») или модификацию для разреженных графов.

Алгоритм Беллмана–Форда

Беллман–Форд — алгоритм поиска кратчайших путей от одной вершины, который умеет работать с отрицательными весами рёбер и дополнительно умеет обнаруживать циклы отрицательного веса (negative cycles). Аналогия: если Дейкстра — это навигатор, всегда выбирающий ближайший необработанный город, то Беллман–Форд — это «лобовой» способ: расслабляем все рёбра снова и снова, пока что-то улучшается.

Почему достаточно V − 1 итераций? В простом пути (без циклов) не больше V − 1 ребра, и каждая итерация гарантированно «продвигает» кратчайший путь хотя бы на одну вершину. Если на V-й итерации релаксация всё ещё возможна — значит, существует цикл, проходя по которому расстояние бесконечно уменьшается, и кратчайшие пути не определены.

struct Edge { int u, v, w; };

// Возвращает dist; при цикле отрицательного веса — пустой вектор
std::vector<long long> bellmanFord(int n, int s, const std::vector<Edge> &edges) {
    const long long INF = 4e18;
    std::vector<long long> dist(n, INF);
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++)
        for (const Edge &e : edges)
            if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;
    for (const Edge &e : edges)                  // проверка цикла отрицательного веса
        if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v]) return {};
    return dist;
}

Практические подсказки:

• Проверка dist[e.u] < INF обязательна: без неё INF + w переполнится и даст мусор вместо «недостижимо».
• Сложность O(V·E) — заметно медленнее Дейкстры, поэтому используйте Беллман–Форд только когда есть отрицательные веса, либо когда нужно гарантированно найти цикл отрицательного веса.
• Типичная ошибка: забыть, что алгоритм работает с ориентированными графами «как есть». В неориентированном графе каждое ребро (u, v, w) нужно добавить в список дважды — в виде (u, v, w) и (v, u, w) — иначе второе направление просто не будет расслабляться.
• Если нужны только пути из одной вершины, но граф большой, можно применять SPFA (Shortest Path Faster Algorithm) — вариант с очередью, который на практике часто быстрее, хотя в худшем случае остаётся O(V·E).

Алгоритм Флойда–Уоршелла

Флойд–Уоршелл — алгоритм поиска кратчайших путей между всеми парами вершин. Идея в одну строку: «разрешаем использовать вершины 0..k как промежуточные и пересчитываем матрицу». Аналогия: сначала мы умеем летать только напрямую, потом — с одной пересадкой в первой вершине, потом — с пересадкой в одной из первых двух, и так далее, пока не разрешим пересадки вообще везде.

Формула d[i][j] = min(d[i][j], d[i][k] + d[k][j]) буквально говорит: «если идти из i в j через k короче, чем текущий лучший путь — обнови». Внешний цикл обязан идти по k (промежуточным вершинам) — это ключ ко всему алгоритму.

void floydWarshall(std::vector<std::vector<long long>> &d) {
    int n = (int)d.size();
    for (int k = 0; k < n; k++)            // k — промежуточная вершина, внешний цикл!
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] < LLONG_MAX && d[k][j] < LLONG_MAX)
                    d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}

Практические подсказки:

• Сложность O(V³) и потребление O(V²) памяти — алгоритм применим для V ≤ 400–500. Для разреженных больших графов используйте V запусков Дейкстры.
• Отрицательные рёбра допустимы, но отрицательные циклы — нет: их видно по диагонали d[i][i] < 0 после выполнения алгоритма (можно бесконечно уменьшать путь i → i через такой цикл).
• Проверка d[i][k] < LLONG_MAX && d[k][j] < LLONG_MAX защищает от переполнения при сложении INF + INF. Использовать LLONG_MAX опаснее, чем 4e18, — последний стабильнее работает с произвольными весами.
• Типичная ошибка: поставить цикл по k внутрь (например, i → k → j). Тогда алгоритм перестанет учитывать пути, использующие несколько промежуточных вершин, и будет выдавать неверные ответы.
• Типичная ошибка №2: инициализировать матрицу расстояний нулями или не тем значением. Корректный старт — d[i][i] = 0, d[i][j] = вес ребра(i, j) (если ребро есть) и ∞ для остальных пар.

Минимальное остовное дерево: Краскал и Прим

Остовное дерево (spanning tree) связного графа — это подграф, который содержит все вершины исходного графа, является деревом (нет циклов) и остаётся связным. Простой образ: взять сетку дорог между городами и убрать «лишние» дороги так, чтобы из любого города можно было добраться в любой другой ровно одним путём. Минимальное остовное дерево (MST) — то из них, у которого суммарный вес рёбер наименьший.

• Краскал: сортирует все рёбра по весу и жадно добавляет их, если они не создают цикл. Цикл проверяется через DSU (Disjoint Set Union, «система непересекающихся множеств») — структуру, которая быстро отвечает на вопрос «вершины u и v уже в одной компоненте?». Сложность O(E log E) (сортировка + почти линейная работа DSU).
• Прим: растёт дерево из одной стартовой вершины, на каждом шаге добавляя самое дешёвое ребро, ведущее наружу — в вершину, ещё не входящую в дерево. Сложность O(E log V) с приоритетной очередью (или O(V²) без неё, что выгодно для плотных графов).

Аналогия для Краскала: представьте, что вы раскладываете провода между компьютерами по минимальной цене — берёте самый дешёвый провод, кладете, если он не замыкает цепь, иначе берёте следующий. Для Прима: вы стоите в одном городе и каждый раз пристраиваете ближайший ещё не подключённый город.

struct WeightedEdge { int u, v, w; };

long long kruskal(int n, std::vector<WeightedEdge> edges) {
    std::sort(edges.begin(), edges.end(),
              [](const WeightedEdge &a, const WeightedEdge &b) { return a.w < b.w; });
    DSU dsu(n);
    long long total = 0;
    int used = 0;
    for (const WeightedEdge &e : edges)
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            if (++used == n - 1) break;      // дерево построено
        }
    return used == n - 1 ? total : -1;       // -1: граф несвязен
}

Практические подсказки:

• В неориентированном графе каждое ребро добавляется один раз — оба конца равноправны.
• Возврат -1 (или отдельный флаг) удобен, когда заранее неизвестно, связен ли граф. В олимпиадных задачах обычно дают связный граф, но подстраховка не помешает.
• Краскал или Прим? Если рёбер мало (E ≈ V) — Краскал. Если граф плотный — Прим с O(V²) (без кучи) часто быстрее.
• Типичная ошибка: забыть, что unite возвращает false, если вершины уже в одном множестве. Без этой проверки вы добавите ребро, замыкающее цикл, и сумма перестанет быть минимальной.
• Типичная ошибка №2: использовать int для суммы весов — для больших графов long long безопаснее.

Пожалуйста, вставьте текст шпаргалки (в формате Markdown), которую нужно улучшить, — и я сразу применю все правила:

• сохраню все заголовки и их иерархию;
• оставлю код в тройных обратных кавычках дословно;
• сохраню структуру таблиц;
• добавлю простые определения, аналогии, объяснения «почему так», практические подсказки и разбор типичных ошибок;
• верну только улучшенный Markdown без лишних комментариев.

Динамическое программирование

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

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

Аналогия из жизни. Представьте лестницу из N ступеней. Сколькими способами можно подняться наверх, шагая за раз на 1 или 2 ступени? Чтобы узнать число способов на ступень i, достаточно знать ответы для i-1 и i-2. Считаем снизу вверх, и каждая ступень «помнит» только своих предшественников. Точно так же ДП избавляет от повторной работы: мы запоминаем уже посчитанные ответы в таблице и переиспользуем их.

Идея в одном предложении: не пересчитывать одно и то же, а хранить промежуточные ответы в массиве/таблице и доставать их за O(1).

Два стиля реализации ДП:

• Мемоизация (top-down, «сверху вниз») — пишем рекурсию, но сохраняем её результаты в массиве/словаре. Удобно, когда состояний потенциально много, но реально нужны лишь некоторые.
• Табуляция (bottom-up, «снизу вверх») — заполняем таблицу итеративно в правильном порядке. Обычно экономнее по памяти и быстрее на практике (нет накладных расходов на рекурсивные вызовы и стек).

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

Практическая подсказка. Чтобы решить задачу ДП, ответьте себе на три вопроса:

1. Что такое состояние? (какие параметры полностью описывают подзадачу)
2. Какой переход? (как из меньших состояний получить текущее)
3. Какой базовый случай и в каком порядке обходить таблицу?

Числа Фибоначчи

Определение. Числа Фибоначчи — последовательность, в которой каждое следующее число равно сумме двух предыдущих: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Это «hello, world» динамического программирования: наивная рекурсия работает за экспоненциальное время O(2ⁿ) из-за повторного пересчёта одних и тех же аргументов, а ДП — за O(n) по времени и O(1) по памяти.

Почему наивно рекурсивно — плохо? Дерево вызовов растёт как бинарное: fib(5) дважды считает fib(3), трижды — fib(2) и так далее. Для n=40 наивный код будет работать заметно, а для n=50 — десятки секунд. ДП хранит только два последних значения, потому что каждое новое число зависит лишь от пары предыдущих — ни старые значения, ни массив целиком не нужны.

// Итеративно: O(n) время, O(1) память
long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    return a;
}

Разбор кода. Переменная a хранит F(i), b — F(i+1). После каждой итерации сдвигаем «окно» вперёд: новая пара — (b, a+b). Цикл крутится n раз, поэтому для n=0 возвращается a=0, для n=1 — a=1, для n=5 — 5. Именно такая схема «два бегунка» обобщается на любую линейную рекуррентность.

Типичные ошибки.

• Переполнение int: уже F(47) не помещается в int, поэтому используем long long.
• Неверное начальное значение b: если b=0 вместо 1, последовательность будет вырожденной (0,0,0,...).
• Возврат b вместо a: легко спутать, какая переменная соответствует F(i), а какая — F(i+1).

Задача о рюкзаке (0/1)

Определение. Задача о рюкзаке 0/1: даны n предметов, у каждого есть вес wᵢ и стоимость vᵢ, а также рюкзак вместимости W. Нужно выбрать набор предметов максимальной суммарной стоимости так, чтобы суммарный вес не превышал W, причём каждый предмет можно взять не более одного раза (отсюда «0/1»).

Аналогия из жизни. Вы собираетесь в поход с рюкзаком на 10 кг. Перед вами 7 вещей разной полезности и веса. Брать предмет можно только целиком и не более одного раза. Хочется унести максимально ценный набор — для этого и нужен перебор «брать/не брать», который ДП сворачивает в линейный по W.

Состояние и переход. Состояние dp[w] — лучшая (максимальная) суммарная стоимость, которую можно набрать при вместимости рюкзака ровно w. Для каждого предмета мы решаем: оставить dp[w] как есть (не брать предмет) или обновить значением dp[w - weight[i]] + value[i] (взять предмет, если он помещается).

Почему цикл идёт с конца? Это критически важно. Если бы мы шли от w = weight[i] к W, то при пересчёте dp[w] уже использовалось бы обновлённое dp[w - weight[i]], в котором этот же предмет был бы «взят» — и мы фактически взяли бы его дважды. Итерация сверху вниз по w гарантирует, что при вычислении dp[w] значение dp[w - weight[i]] ещё соответствует состоянию без текущего предмета. Для неограниченного рюкзака (можно брать предмет многократно) — наоборот, цикл идёт снизу вверх.

// 0/1-рюкзак: O(n·W) время, O(W) память
int knapsack(const std::vector<int> &weight, const std::vector<int> &value, int W) {
    std::vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < weight.size(); i++)
        for (int w = W; w >= weight[i]; w--)            // с конца — иначе предмет возьмётся дважды
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[W];
}

Оптимизация памяти. Мы храним только одномерный массив длины W+1, потому что переход зависит лишь от уже посчитанных (на этой же итерации) значений dp[w] и dp[w - weight[i]]. Полная таблица dp[i][w] тоже работает, но требует O(n·W) памяти.

Типичные ошибки.

• Забыть обнулить dp — без vector<int>(W + 1, 0) массив будет забит мусором.
• Использовать int при больших W и vᵢ: суммарная стоимость может не поместиться, берите long long.
• Перепутать направление цикла по w: для задачи неограниченного рюкзака нужен цикл for (int w = weight[i]; w <= W; w++), а для 0/1 — наоборот.

Наибольшая общая подпоследовательность (LCS)

Определение. LCS (Longest Common Subsequence) двух строк a и b — самая длинная последовательность символов, которая встречается в обеих строках в том же относительном порядке, но не обязательно подряд. Например, LCS строк "ABCBDAB" и "BDCAB" имеет длину 4 (например, "BCAB" или "BDAB").

Аналогия из жизни. Сравниваем две версии одного документа. Хотим понять, какая часть текста осталась общей (не вырезанной, не переставленной) — это и есть LCS. Похоже на поиск общего паттерна в ДНК двух родственных видов.

Состояние и переход. dp[i][j] — длина LCS префиксов a[0..i-1] и b[0..j-1]. Если последние символы префиксов равны (a[i-1] == b[j-1]), их можно «приклеить» к общему хвосту: dp[i][j] = dp[i-1][j-1] + 1. Если не равны — пробуем отрезать последний символ у одной из строк и берём лучшее из двух вариантов: max(dp[i-1][j], dp[i][j-1]).

Почему база — нулевая строка? Когда одна из строк пустая, общая подпоследовательность тоже пустая, длина 0. Поэтому dp[0][*] = dp[*][0] = 0, и мы заполняем таблицу от (1,1) до (n,m).

int lcs(const std::string &a, const std::string &b) {
    int n = (int)a.size(), m = (int)b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a[i - 1] == b[j - 1])
                ? dp[i - 1][j - 1] + 1
                : std::max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}

Оптимизация памяти. Так как текущий dp[i][j] зависит только от dp[i-1][j-1], dp[i-1][j] и dp[i][j-1], можно хранить лишь две строки (предыдущую и текущую) — это схема из задачи Левенштейна ниже.

Типичные ошибки.

• Сравнивать a[i] с b[j] вместо a[i-1] с b[j-1] — массив-то размера n+1 на m+1, а строка — без фиктивного нулевого символа.
• Считать подстроку вместо подпоследовательности (для подстроки нужен другой алгоритм за O(n·m) с условием непрерывности).
• Использовать std::string для очень больших входов без предварительного резервирования.

Наибольшая возрастающая подпоследовательность (LIS)

Определение. LIS (Longest Increasing Subsequence) — самая длинная строго возрастающая подпоследовательность массива (элементы идут по индексам в исходном порядке, но не обязательно подряд). Например, для [3, 1, 4, 1, 5, 9, 2, 6] LIS имеет длину 4 — это, например, [1, 4, 5, 9] или [1, 2, 5, 6].

Аналогия из жизни. Перед вами очередь из коробок разной высоты. Хотите выбрать как можно больше коробок так, чтобы каждая следующая была выше предыдущей, но нельзя переставлять коробки. Это и есть LIS.

Два подхода.

• Наивное ДП за O(n²): dp[i] — длина LIS, заканчивающейся в позиции i. Переход: dp[i] = max(dp[j] + 1) по всем j < i, где a[j] < a[i].
• Метод с lower_bound за O(n log n): храним массив tail, где tail[k] — минимально возможный последний элемент возрастающей подпоследовательности длины k+1. Для каждого нового числа x находим в tail позицию для x через lower_bound (первый элемент ≥ x) и заменяем: это «улучшает» хвост — меньший последний элемент оставляет больше шансов продолжить подпоследовательность дальше.

Почему работает lower_bound? tail всегда отсортирован по возрастанию. Если x больше всех хвостов, мы продлеваем самую длинную подпоследовательность (длина увеличивается). Если x «встраивается» куда-то в середину, мы уменьшаем последний элемент подпоследовательности этой длины — от этого она может только стать «перспективнее», длина не меняется.

Чем lower_bound отличается от upper_bound? lower_bound заменяет первый ≥ x — это даёт строго возрастающую подпоследовательность. Если нужна неубывающая, берите upper_bound (заменяет первый > x).

// LIS за O(n log n)
int lis(const std::vector<int> &a) {
    std::vector<int> tail;                  // tail[k] — лучший конец для длины k+1
    for (int x : a) {
        auto it = std::lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;                       // заменяем на меньший конец
    }
    return (int)tail.size();
}

Практическая подсказка. Этот метод возвращает только длину. Чтобы восстановить саму подпоследовательность, придётся дополнительно хранить массив «предков» — индекс того элемента, из которого мы пришли.

Типичные ошибки.

• Путать строгую и нестрогую возрастающую подпоследовательность (меняется выбор между lower_bound и upper_bound).
• Считать длину самой tail длиной LIS — это и правда длина, но сам массив tail не является LIS, он лишь хранит «оптимальные хвосты».
• Использовать линейный поиск вместо lower_bound — теряется асимптотика O(n log n).

Расстояние Левенштейна

Определение. Расстояние Левенштейна (редакционное расстояние) — это минимальное число операций вставки, удаления и замены символа, необходимых, чтобы превратить строку a в строку b. Например, kitten → sitting: заменить k на s, заменить e на i, вставить g в конец → расстояние 3.

Аналогия из жизни. Это мера того, насколько сильно отличаются два текста, если разрешено только три «карандашных» операции: стереть букву, дописать букву, зачеркнуть и вписать другую. Используется в проверке орфографии, поиске похожих слов и в биоинформатике (сравнение ДНК).

Состояние и переход. dp[i][j] — расстояние между префиксами a[0..i-1] и b[0..j-1]. База: превратить пустую строку в b[0..j-1) можно только j вставками; аналогично удалить все i символов — i удалений. Переход:

• Удаление символа из a: prev[j] + 1.
• Вставка символа в a (чтобы соответствовать b): cur[j-1] + 1.
• Замена (или «бесплатное совпадение»): prev[j-1] + (a[i-1] != b[j-1]) — то есть +1 при замене и +0 при совпадении.

Почему две строки prev и cur? Полная таблица dp[n+1][m+1] занимает O(n·m) памяти. Но текущий dp[i][j] зависит только от предыдущей строки dp[i-1][*] и уже посчитанных элементов текущей строки. Поэтому храним всего две строки и в конце обмениваем их — это даёт O(m) памяти при той же асимптотике O(n·m) по времени.

Почему в конце возвращаем prev[m]? После последнего swap строка prev содержит только что посчитанную «текущую» строку для i = n.

int levenshtein(const std::string &a, const std::string &b) {
    int n = (int)a.size(), m = (int)b.size();
    std::vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; j++) prev[j] = j;          // превратить пустое в b[0..j)
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++)
            cur[j] = std::min({prev[j] + 1,             // удаление
                               cur[j - 1] + 1,          // вставка
                               prev[j - 1] + (a[i - 1] != b[j - 1])});  // замена
        std::swap(prev, cur);
    }
    return prev[m];
}

Типичные ошибки.

• Забыть prev[j] = j перед основным циклом — без базы первый столбец/строка будут заполнены мусором.
• Сравнивать a[i] с b[j] вместо a[i-1] с b[j-1] (та же ошибка индексации, что в LCS).
• Считать «расстояние Хэмминга» (только замены) вместо Левенштейна — у Хэмминга другая формула и нет операций вставки/удаления.

Задача о монетах

Определение. Задача о размене (coin change): дан набор номиналов монет coins и целевая сумма S. Нужно найти минимальное число монет, которыми можно набрать ровно S, или определить, что это невозможно. Каждый номинал можно использовать неограниченно (в отличие от 0/1-рюкзака).

Аналогия из жизни. Вы стоите у кассы и хотите заплатить 63 рубля монетами по 1, 5, 10 и 25 рублей так, чтобы отдать как можно меньше монет. Это и есть задача о монетах, только в реальности кассир ещё учитывает ограничения в наличии — здесь же их нет.

Состояние и переход. dp[s] — минимальное число монет, которыми можно набрать сумму s. База: dp[0] = 0 (пустая сумма — без монет). Все остальные dp[s] инициализируются «бесконечностью» (INF). Для каждой суммы s мы пробуем каждую монету c ≤ s: если через неё удаётся добраться до s дешевле, обновляем dp[s] = dp[s-c] + 1. Если после перебора всех монет dp[S] осталось равным INF, набрать S нельзя.

Почему INF = 1e9? Это значение должно быть заведомо больше любого возможного ответа. S + 1 — слишком мало при S = 0, 1e9 — универсальная и безопасная константа (если только вы не уверены, что ответ точно меньше).

// Минимальное число монет; -1, если набрать нельзя
int coinChange(const std::vector<int> &coins, int S) {
    const int INF = 1e9;
    std::vector<int> dp(S + 1, INF);
    dp[0] = 0;
    for (int s = 1; s <= S; s++)
        for (int c : coins)
            if (c <= s && dp[s - c] + 1 < dp[s]) dp[s] = dp[s - c] + 1;
    return dp[S] >= INF ? -1 : dp[S];
}

Разница с 0/1-рюкзаком. Здесь внутренний цикл идёт по сумме (s), а внешний — по монетам, и направление по s может быть любым (хоть сверху вниз, хоть снизу вверх). Это и даёт неограниченное использование монет.

Вариации задачи.

• Посчитать число способов размена — заменить минимум на сумму, dp[0] = 1, остальные нули.
• Неограниченный рюкзак по стоимости — ищем максимум стоимости при заданной вместимости.
• Можно ли набрать сумму вообще — dp[0] = true, остальное false, переход через dp[s] |= dp[s-c].

Типичные ошибки.

• Инициализировать dp нулями — тогда минимум всегда будет 0 или 1 (в зависимости от знака), что бессмысленно.
• Забыть проверку c <= s — без неё обращение к dp[s-c] при s < c уйдёт в отрицательный индекс.
• Не отличать «нельзя набрать» (dp[S] == INF) от «набирается нулем монет» (на самом деле невозможно при S > 0, но при S == 0 ответ именно 0, а не -1).

Сводная таблица ДП

Жадные алгоритмы и «разделяй и властвуй»

Жадный алгоритм (greedy algorithm) — это стратегия, в которой на каждом шаге принимается решение, выглядящее лучшим в данный момент, и больше оно не пересматривается. Похоже на поведение человека в очереди за пиццей, который хватает самый большой видимый кусок, не задумываясь, останется ли место для десерта — иногда это работает идеально, а иногда приводит к далеко не оптимальному итогу.

Жадный алгоритм на каждом шаге делает локально оптимальный выбор и не пересматривает его. Это быстро и просто, но корректно далеко не всегда: нужны свойства жадного выбора и оптимальной подструктуры (их доказывают обменным аргументом).

Почему «локально оптимум» ≠ «глобально оптимум»? Потому что жадный выбор оптимизирует только текущий момент, не учитывая влияние на будущее. Чтобы жадный алгоритм был корректным, задача должна обладать двумя математическими свойствами:

• Свойство жадного выбора (greedy choice property): существует оптимальное решение, в котором первый шаг совпадает с жадным выбором. То есть «пожадничав» один раз, мы всё ещё можем достроить решение до глобального оптимума.
• Оптимальная подструктура (optimal substructure): после жадного выбора оставшаяся подзадача имеет тот же тип, и её оптимальное решение можно «склеить» с уже сделанным выбором.

Доказывают корректность обычно обменным аргументом (exchange argument): берут произвольное оптимальное решение и показывают, что в нём жадный выбор можно «поменять местами» с первым шагом без ухудшения результата. Затем по индукции то же самое повторяется для подзадачи.

Когда жадный корректен

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

• Код Хаффмана: строим дерево, каждый раз сливая два узла с наименьшими частотами (через кучу). Даёт оптимальный префиксный код. Почему так: редкие символы «прячутся» глубже в дереве (получают длинный код), а частые — ближе к корню (короткий код). Если бы мы сливали большие частоты первыми, редкие символы стали бы ещё длиннее и суммарная длина возросла бы. Это буквально та же задача, что и оптимальное слияние файлов.

• Минимальное остовное дерево (MST): алгоритмы Краскала и Прима — жадные и корректные. Подсказка: Краскал сортирует все рёбра и берёт минимальное, которое не создаёт цикл (проверка через Union-Find / DSU). Прим растёт из одной вершины, на каждом шаге добавляя минимальное ребро к уже построенному «фронту» (через priority queue). Оба корректны, потому что любое MST можно «отредактировать» так, чтобы оно начиналось с жадного ребра.

• Слияние файлов: жадно сливать два наименьших — оптимум. Почему: стоимость слияния — сумма размеров сливаемых файлов. Если всегда сливать самые маленькие, общая стоимость минимальна (классический результат; формально доказывается обменным аргументом или эквивалентностью задачи коде Хаффмана — суммарная стоимость слияния равна сумме freq·depth).

• Покрытие отрезками (interval covering / minimum number of intervals): жадное покрытие (выбирать отрезок с самым дальным правым концом среди покрывающих текущую «дыру») оптимально. Аналогия: нужно добраться из точки A в точку B прыжками фиксированной длины; всегда прыгайте так далеко, как можете — потратите минимум прыжков.

Когда жадный ломается

• Размен монет: жадность «брать самую крупную» работает для канонических систем (1, 5, 10, 25 — доллар; 1, 2, 5, 10 — рубли/евроценты тоже канонические), но не для произвольных. Контрпример: монеты {1, 3, 4} и сумма 6 — жадно 4 + 1 + 1 (3 монеты), а оптимально 3 + 3 (2 монеты). Типичная ошибка: считать, что если жадный работает для «обычных» монет, он работает всегда. Каноничность системы монет — отдельное свойство, которое нужно явно проверять (например, для {1, 3, 4} сумма 6 уже даёт контрпример). Если нужна гарантия для произвольных наборов — используйте ДП.

• Задача о рюкзаке 0/1: жадность «по удельной стоимости» (сортируем предметы по value/weight и берём максимум) неоптимальна; она точна только для дробного рюкзака (где предмет можно разрезать и взять часть). Контрпример: рюкзак вместимости 10, предметы A (вес 6, ценность 7), B (вес 5, ценность 5), C (вес 5, ценность 5). Удельная стоимость: A ≈ 1.17, B = 1, C = 1. Жадно берём A, остаётся 4 единицы — ничего не влезает, итоговая ценность 7. А оптимально: B + C = 10, ценность 10.

• Коммивояжёр (TSP): эвристика «ближайший сосед» даёт плохое приближение. Почему: на последнем шаге может оказаться, что мы «застряли» в дальнем городе и возвращение стоит дорого. В худшем случае такой жадный даёт в разы более длинный маршрут, чем оптимальный. Для гарантированного 2-приближения используют обход MST (удвоение) или алгоритм Кристофидеса (1.5-приближение для метрического TSP).

Если жадный не проходит — переходите к динамическому программированию (ДП). На экзамене часто просят именно контрпример, поэтому держите в голове размен {1, 3, 4} и сумму 6.

Практический совет: прежде чем писать жадный алгоритм на собеседовании или экзамене, потратьте 30 секунд на попытку построить контрпример — это быстрее, чем потом переписывать код на ДП. Универсальная схема проверки: придумайте 3 предмета/интервала/монеты, переберите 2–3 варианта вручную и сравните с жадным выбором.

Парадигма «разделяй и властвуй»

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

Три шага любого алгоритма «разделяй и властвуй» (D&C):

1. Divide (разделить) — разбить задачу на k подзадач меньшего размера (чаще всего k = 2).
2. Conquer (покорить) — рекурсивно решить каждую подзадачу. Если подзадача достаточно мала (база рекурсии), решить напрямую без рекурсивных вызовов.
3. Combine (объединить) — собрать решения подзадач в решение исходной задачи. Стоимость объединения — главный фактор итоговой сложности.

Аналогия из жизни: военная стратегия — большую армию разбивают на корпуса, корпус — на полки, полки ведут бой независимо, потом объединяют результаты. Или сортировка стопки карточек по алфавиту: делите стопку пополам, сортируете каждую отдельно, потом сливаете отсортированные половины — это merge sort.

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

// Быстрое возведение в степень: O(log n)
long long power(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result *= base;       // младший бит — умножаем
        base *= base;
        exp >>= 1;                         // делим показатель пополам
    }
    return result;
}

Как читать этот код (пошагово):

• На каждой итерации мы смотрим на младший бит показателя степени (exp & 1).
• Если бит = 1, текущее base нужно включить в произведение — домножаем на result.
• Затем возводим base в квадрат (переход к следующему биту) и сдвигаем показатель вправо (exp >>= 1).
• По сути это схема Горнера для многочлена по основанию 2: base^exp = ∏ base^(2^i) по тем i, где соответствующий бит показателя равен 1.

Асимптотика. Число итераций равно числу бит в exp, то есть O(log exp). Формально рекуррентность для рекурсивной версии T(n) = T(n/2) + O(1) по мастер-теореме даёт O(log n). Память — O(1) в этой итеративной версии (рекурсивная требовала бы O(log n) на стек).

Типичные ошибки:

• Забыть тип long long и получить целочисленное переполнение при больших base или exp (особенно если нужна проверка по модулю).
• Перепутать порядок строк: base *= base должно быть ДО exp >>= 1, иначе при следующей итерации мы будем домножать не на ту степень.
• Не обработать случай exp = 0 (должно вернуть 1 — этот код корректно работает, проверьте мысленно: цикл не запустится, вернётся result = 1).
• Не учитывать отрицательный exp: для целых степеней с отрицательным показателем нужно либо работать с дробными/рациональными числами, либо считать по модулю через быстрое возведение с обратным элементом.

Связь с «разделяй и властвуй»: здесь задача «вычислить base^exp» делится на две независимые подзадачи — «base^(exp/2)» и (опционально) «base * base^(exp/2)» при нечётном показателе. Размер подзадачи уменьшается вдвое на каждом шаге, объединение — одно умножение, отсюда O(log n).

Полезные приёмы

Эти техники чаще всего отделяют решение «в лоб» от проходящего по времени. Их нужно узнавать по формулировке.

Что значит «узнавать по формулировке»? В условии почти всегда есть подсказка-маркер: «в отсортированном массиве», «сумма на отрезке», «окно», «не более k различных» и т. п. Увидели такой маркер — сразу вспоминайте соответствующий приём.

Два указателя

Определение. Два указателя (two pointers) — это техника, при которой по массиву или строке одновременно движутся два индекса (l и r). Они могут идти навстречу друг другу, в одном направлении с разной скоростью или от разных «стартов». Каждый шаг сдвигает один из указателей — благодаря этому двойной цикл O(n²) превращается в линейный O(n).

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

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

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

• задача о паре/тройке с заданной суммой на отсортированных данных;
• удаление дубликатов с сохранением порядка;
• разворот массива/строки на месте;
• слияние двух отсортированных массивов;
• задачи на палиндромы (указатели с двух концов строки).

Типичные ошибки:

• Забыть условие l < r — без него указатели «перескочат» друг друга и могут посчитать один и тот же элемент дважды.
• Применять к неотсортированному массиву — без сортировки монотонность нарушается и алгоритм перестаёт быть корректным.
• Использовать знаковое сравнение s < target при больших числах — есть риск переполнения int (используйте long long).

// Есть ли пара с суммой target в ОТСОРТИРОВАННОМ массиве — O(n)
bool hasPair(const std::vector<int> &a, int target) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return true;
        if (s < target) l++;               // нужно больше — сдвигаем левый
        else r--;
    }
    return false;
}

Скользящее окно

Определение. Скользящее окно (sliding window) — это непрерывный отрезок массива фиксированной или переменной длины, который «скользит» по данным. На каждом шаге окно сдвигается на одну позицию, а поддерживаемая характеристика (сумма, максимум, количество уникальных элементов и т. п.) обновляется за O(1) — обычно вычитанием элемента, ушедшего из окна, и прибавлением вошедшего.