Хеш-таблицы и префиксные суммы: структуры для мгновенного поиска и анализа отрезков

Хеш-таблицы в Python: внутреннее устройство dict и set для поиска за O(1)

Представьте, что вам нужно найти книгу в огромной библиотеке, где миллионы томов расставлены в случайном порядке. Если вы будете проверять каждую книгу одну за другой, это займет недели. Но что, если у вас есть магический индекс: вы произносите название книги, и она мгновенно оказывается у вас в руках? В мире алгоритмов такой «магией» обладают хеш-таблицы. В Python они реализованы через типы dict (словари) и set (множества). Именно понимание того, как эти структуры достигают константного времени поиска , отделяет крепкого разработчика от новичка, для которого словарь — это просто «удобное хранилище».

Механика «мгновенного» доступа

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

Проблема в том, что память компьютера — это линейный массив ячеек. Чтобы превратить произвольный ключ (например, строку "user_1234") в индекс массива, используется хеш-функция.

Роль хеш-функции

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

> «Если два объекта равны, их хеш-значения обязаны быть равны. Однако если хеш-значения равны, объекты не обязательно равны». > > Документация Python: Data Model

Чтобы объект мог быть ключом в словаре или элементом множества, он должен быть хешируемым (hashable). Это накладывает два условия:

Объект должен иметь хеш-значение, которое не меняется в течение его жизни.

Объект должен поддерживать сравнение с другими объектами (__eq__).

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

От хеша к индексу

Получив огромное число от hash(key), Python должен сопоставить его с конкретной ячейкой в массиве (слоте) внутри хеш-таблицы. Самый простой способ сделать это — взять остаток от деления: index = hash(key) % capacity, где capacity — текущий размер внутреннего массива.

Однако в Python используется более сложная битовая маска, так как размер таблицы всегда является степенью двойки (). Это позволяет заменить дорогостоящую операцию деления на быструю битовую операцию AND: index = hash(key) & (capacity - 1).

Анатомия коллизий и методы их решения

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

Метод цепочек (Chaining): Каждая ячейка массива содержит список (или связный список) всех элементов, попавших в этот индекс. Если коллизий много, поиск в такой «цепочке» деградирует до .

Открытая адресация (Open Addressing): Если ячейка занята, алгоритм ищет другую свободную ячейку по определенному правилу.

Python использует открытую адресацию. Если происходит коллизия, Python применяет алгоритм пробирования (probing), чтобы найти следующий слот. Формула вычисления следующего индекса в Python сложнее, чем просто «шаг вправо». Она учитывает неиспользованные биты хеша, чтобы быстрее распределить ключи по таблице и избежать кластеризации (скопления занятых ячеек в одном месте).

Почему поиск остается O(1)?

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

Ключевой параметр здесь — Load Factor (коэффициент заполнения).

где — количество элементов в таблице, — общее количество слотов.

Как только коэффициент заполнения превышает определенный порог (в Python это ), структура данных автоматически увеличивается в размере (обычно в 2 или 4 раза), и все существующие элементы перераспределяются по новым местам (rehashing). Это дорогая операция , но она происходит редко, поэтому среднее время остается константным.

Эволюция словарей в Python: компактность и порядок

До версии Python 3.6 словари были довольно «прожорливыми» до памяти. Внутренняя структура представляла собой один большой массив, где каждая ячейка содержала:

Хеш ключа.

Ссылку на объект-ключ.

Ссылку на объект-значение.

Поскольку массив должен быть разреженным (чтобы минимизировать коллизии), в нем было много пустых ячеек (dummy slots), каждая из которых занимала 24 байта (на 64-битных системах).

Начиная с Python 3.6 (и официально с 3.7), структура словаря изменилась. Теперь она состоит из двух массивов:

Indices: Компактный массив целых чисел (байтов), который играет роль хеш-таблицы.

Entries: Плотный массив, содержащий сами данные [hash, key, value].

Теперь, когда мы ищем ключ, мы сначала идем в массив Indices. Его размер подбирается так, чтобы он был разреженным, но так как он хранит только маленькие целые числа, он занимает мало места. Найдя там индекс, мы обращаемся к массиву Entries по этому индексу.

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

Множества (set) vs Словари (dict)

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

| Характеристика | dict | set | | :--- | :--- | :--- | | Хранение | Пары ключ-значение | Только уникальные ключи | | Поиск | key in d — | item in s — | | Память | Выше (хранит ссылки на значения) | Ниже | | Применение | Хранение состояний, счетчики | Проверка уникальности, пересечения |

Важно помнить, что проверка if x in collection для списка занимает , а для множества — . В задачах Яндекса это часто является ключом к оптимизации: замена поиска в списке на поиск в множестве превращает квадратичный алгоритм в линейный.

Тонкие моменты и ловушки производительности

Несмотря на магическое , существуют сценарии, где хеш-таблицы могут стать узким местом.

1. Плохие хеш-функции и Hash Collision Attack

Если злоумышленник знает алгоритм хеширования (а в Python он открыт), он может подобрать такие ключи, у которых хеши будут идентичны по модулю размера таблицы. Это приведет к тому, что все элементы попадут в одну цепочку коллизий, и поиск станет . Для защиты от этого Python использует соль (hash randomization) — случайное значение, которое добавляется к хешу строк при запуске интерпретатора. Поэтому hash("apple") будет разным в разных сессиях Python.

2. Мутабельность и хешируемость

Частая ошибка — попытка использовать список как ключ.

Решение — использовать кортеж (tuple), который является неизменяемым: data[tuple(coords)] = "Point A". Однако будьте осторожны: кортеж хешируем только в том случае, если все его элементы хешируемы. Кортеж ([1, 2], 3) вызовет ошибку.

3. Оценка памяти

Хеш-таблицы всегда потребляют больше памяти, чем массивы. Если у вас миллиард мелких объектов, dict может поглотить всю RAM. В таких случаях стоит рассмотреть __slots__ в классах или специализированные структуры из библиотеки numpy.

Практическое применение: паттерн «Частотный словарь»

Одна из самых классических задач, где хеш-таблицы показывают свою мощь — это подсчет вхождений элементов.

Представьте задачу: дан массив чисел, нужно найти число, которое встречается чаще всего.

Наивное решение: Для каждого числа пройтись по всему массиву и посчитать его копии. Сложность .

Решение с хеш-таблицей:

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

Сравнение объектов и производительность хеширования

Когда вы вызываете d[key], Python выполняет следующие шаги:

Вычисляет h = hash(key).

Ищет слот i = h & mask.

Если слот занят объектом other_key, Python сначала проверяет их хеши.

Если hash(key) == hash(other_key), только тогда вызывается key == other_key.

Это критически важная оптимизация. Сравнение целых чисел (хешей) выполняется мгновенно на уровне процессора. Сравнение сложных объектов (например, длинных строк или пользовательских классов) может быть медленным. Python вызывает тяжелую операцию __eq__ только в том случае, если хеши совпали, что минимизирует накладные расходы.

Пользовательские объекты как ключи

Вы можете сделать свой класс хешируемым, определив методы __hash__ и __eq__. Это часто требуется в сложных алгоритмах, где состоянием является не просто число, а сложный объект.

Если вы определите __eq__, но забудете __hash__, Python пометит ваш класс как нехешируемый. Это сделано специально, чтобы предотвратить нарушение контракта: «равные объекты — равные хеши».

Когда хеш-таблица не идеальна?

Несмотря на асимптотику , у хеш-таблиц есть «скрытые» константы.

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

Локальность данных: Массивы (листы) лежат в памяти последовательно, что позволяет процессору эффективно использовать кэш. Хеш-таблицы разбрасывают данные по памяти более хаотично, что может приводить к Cache Miss и замедлению на физическом уровне, несмотря на алгоритмическую эффективность.

В задачах на поиск диапазонов (например, «найти все числа от 10 до 100») хеш-таблицы бесполезны, так как они не сохраняют порядок величин. Здесь на сцену выходят деревья поиска или сортированные массивы с бинарным поиском, которые мы разберем в следующих главах.

Хеш-таблицы в контексте префиксных сумм

Эта статья — фундамент для следующего важного паттерна. Часто в задачах Яндекса требуется найти подмассив, сумма которого равна . Наивный подход с двумя указателями здесь не сработает, если в массиве есть отрицательные числа (окно не может расширяться/сужаться монотонно). Однако, используя префиксные суммы в связке с хеш-таблицей, мы сможем решить эту задачу за . Мы будем сохранять в словарь все встреченные значения префиксных сумм и мгновенно проверять, не встречалась ли нам ранее сумма, дополняющая текущую до целевого значения. Но прежде чем переходить к этому мощному симбиозу, необходимо закрепить механику самих префиксов.

Префиксные суммы: техника накопления для мгновенного вычисления суммы на отрезке

Представьте серверную аналитику, которая каждую секунду фиксирует количество запросов к вашему API. За сутки накапливается 86 400 чисел. В конце дня аналитическая система должна ответить на 100 000 вопросов вида: «Сколько запросов пришло с 10:15:30 до 14:20:00?». Если для каждого из 100 000 вопросов мы будем запускать цикл и суммировать элементы массива на заданном отрезке, алгоритм совершит миллиарды операций. Система зависнет на простейшей задаче из-за того, что мы раз за разом пересчитываем одни и те же данные.

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

От квадратичной сложности к константному времени

Наивный подход к вычислению суммы на отрезке от индекса до индекса заключается в прямом переборе. Мы создаем цикл от до включительно и накапливаем результат. Время выполнения одного такого запроса составляет в худшем случае (когда отрезок охватывает весь массив). Если у нас запросов, общая временная сложность составит . При и это приведет к операций, что гарантированно вызовет ошибку Time Limit Exceeded (превышение лимита времени) в любой тестирующей системе Яндекса или LeetCode.

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

Идея состоит в том, чтобы создать новый массив , где каждый элемент хранит сумму всех элементов исходного массива от начала (нулевого индекса) до текущего индекса включительно.

Математически это выглядит так:

!Пошаговое построение массива префиксных сумм

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

Магия вычитания: как получить сумму любого отрезка

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

Допустим, нам нужна сумма элементов с индекса до . В массиве префиксных сумм у нас есть значение , которое равно сумме элементов от до :

Но нам не нужны элементы и . Их нужно отсечь. Сумма этих «лишних» элементов уже заботливо подсчитана и хранится в .

Если мы вычтем из , то получим ровно то, что искали:

!Механика вычисления суммы на отрезке через вычитание префиксов

Обобщая это правило, получаем главную формулу префиксных сумм:

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

Проблема левой границы и паттерн «фиктивного нуля»

Формула безупречна математически, но при реализации в коде она таит в себе ловушку. Что произойдет, если нас попросят найти сумму от самого начала массива, то есть при ?

Формула попытается обратиться к . В языках вроде C++ или Java это приведет к ошибке выхода за пределы массива (Index Out of Bounds). В Python обращение к индексу вернет последний элемент массива, что приведет к совершенно неверному математическому результату, и эту логическую ошибку будет крайне сложно отладить.

Наивное решение — добавить проверку условия (if-statement):

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

Мы создаем массив размером , где всегда равен . Тогда будет хранить сумму первого элемента исходного массива, — сумму первых двух элементов, и так далее. Элемент хранит сумму ровно первых элементов.

Посмотрим, как изменятся индексы. Пусть исходный массив . Длина . Создаем длиной :

Теперь, чтобы найти сумму элементов исходного массива с индекса по индекс (где индексы и относятся к исходному 0-индексированному массиву ), мы используем модифицированную формулу:

Проверим для отрезка от до (элементы , сумма ): . Все верно.

Проверим проблемный случай от до (элементы , сумма ): .

Фиктивный ноль в начале массива элегантно поглотил граничный случай. Нам больше не нужны проверки if L == 0.

Шаблон кода для построения такого массива в Python:

Отличие от скользящего окна

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

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

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

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

Рассмотрим классическую задачу (LeetCode 724: Find Pivot Index). Дан массив целых чисел. Нужно найти такой индекс, при котором сумма всех элементов слева от него равна сумме всех элементов справа от него. Если такого индекса нет, вернуть . Сам элемент на индексе равновесия не включается ни в левую, ни в правую сумму.

Пример: . Ответ: индекс (число ). Сумма слева: . Сумма справа: .

Наивное решение — для каждого индекса запускать два цикла (влево и вправо) — даст . Применив префиксные суммы, мы можем решить задачу за .

Если у нас есть массив префиксных сумм , то для любого индекса : Сумма слева — это просто сумма элементов от до . Сумма справа — это сумма элементов от до конца массива.

Однако эту задачу можно решить еще изящнее, оптимизировав пространственную сложность (Space-Time Tradeoff). Нам не обязательно хранить весь массив префиксных сумм в памяти. Достаточно знать общую сумму всех элементов массива (это последний элемент префиксного массива) и поддерживать текущую сумму слева на лету.

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

Алгоритм становится предельно простым:

Вычисляем общую сумму массива (один проход, ).

Инициализируем .

Проходим по массиву слева направо. Для каждого элемента проверяем условие: .

Если условие выполняется — мы нашли индекс равновесия.

Если нет — добавляем текущий элемент к и переходим к следующему шагу.

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

Обобщение паттерна: префиксные и суффиксные произведения

Концепция префиксного накопления не ограничивается только сложением. Мы можем накапливать умножение (префиксные произведения), побитовый XOR, поиск максимума или минимума на префиксе. Главное условие — операция должна позволять быстро извлекать данные для отрезка.

Рассмотрим задачу, которая часто встречается на собеседованиях уровня Hard (LeetCode 238: Product of Array Except Self). Дан массив . Нужно вернуть массив , где равен произведению всех элементов массива , кроме . Использовать операцию деления запрещено, алгоритм должен работать за .

Пример: . Ожидаемый ответ: . Например, для индекса (число ), произведение остальных чисел: .

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

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

Для любого индекса , произведение всех элементов кроме состоит из двух частей:

Произведение всех элементов строго слева от (префиксное произведение).

Произведение всех элементов строго справа от (суффиксное произведение).

Если мы заранее вычислим префиксные произведения в массив и суффиксные произведения в массив , то ответ для индекса будет равен просто .

Построим эти массивы для . Массив префиксов (где — произведение элементов от до ):

Массив суффиксов (где — произведение элементов от до конца):

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

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

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

Ограничения структуры

Префиксные суммы — невероятно мощный инструмент, но у него есть строгое ограничение: исходный массив должен быть статичным (иммутабельным).

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

Если задача требует чередования запросов на вычисление суммы и запросов на обновление отдельных элементов, префиксные суммы теряют свою эффективность. Для таких динамических сценариев существуют более сложные структуры данных, такие как деревья отрезков (Segment Trees) или деревья Фенвика (Binary Indexed Trees), которые позволяют выполнять обе операции (и запрос суммы, и обновление элемента) за логарифмическое время .

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

Представьте карту города, разбитую на сетку кварталов размером . В каждой ячейке записано количество заказов такси за сутки. Аналитикам нужно найти прямоугольную область размером кварталов с максимальным спросом, чтобы разместить там новый автопарк. Наивный алгоритм будет перебирать все возможные положения квадрата , и для каждого из них заново суммировать ячеек. Для сетки миллион на миллион это приведет к триллионам операций. Однако математика позволяет отвечать на вопрос «какова сумма в любом прямоугольнике» ровно за четыре операции сложения и вычитания, независимо от того, содержит этот прямоугольник четыре ячейки или четыре миллиона.

От одномерного массива к геометрии площадей

В одномерных массивах префиксная сумма накапливает значения слева направо. В двумерном пространстве логика сохраняется, но накопление идет сразу по двум осям: сверху вниз и слева направо.

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

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

Если исходная матрица имеет размер , то префиксная матрица будет иметь размер . Индекс в префиксной матрице будет соответствовать количеству взятых строк, а индекс — количеству взятых столбцов.

Рассмотрим исходную матрицу :

| 1 | 2 | 3 | |---|---|---| | 4 | 5 | 6 | | 7 | 8 | 9 |

Соответствующая ей префиксная матрица будет выглядеть так:

| 0 | 0 | 0 | 0 | |---|---|---|---| | 0 | 1 | 3 | 6 | | 0 | 5 | 12 | 21 | | 0 | 12 | 27 | 45 |

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

Принцип включений-исключений при построении

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

Здесь вступает в силу принцип включений-исключений. Чтобы вычислить площадь нового, чуть большего прямоугольника, мы можем сложить площади известных прямоугольников, вычесть то, что посчитали дважды, и добавить новую деталь.

!Геометрия построения двумерного префиксного массива

Формула вычисления элемента префиксной матрицы выглядит следующим образом:

Разберем каждый элемент этой формулы:

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

— значение текущей ячейки из исходной матрицы. Индексы смещены на единицу назад, так как исходная матрица не имеет фиктивных нулевых строк и столбцов.

— сумма прямоугольника, находящегося строго над нашей ячейкой.

— сумма прямоугольника, находящегося строго слева от нашей ячейки.

— сумма прямоугольника, находящегося по диагонали слева-сверху.

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

!Пошаговое заполнение префиксной матрицы 3x3

Реализация построения на Python требует создания матрицы, заполненной нулями, и двойного цикла:

Пространственная сложность этого алгоритма составляет , так как мы выделяем память под новую матрицу. Временная сложность также .

Мгновенный запрос суммы произвольной подматрицы

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

Пусть нам нужно найти сумму элементов в прямоугольнике, левый верхний угол которого находится в координатах , а правый нижний — в координатах . Индексы относятся к исходной 0-индексированной матрице.

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

!Геометрия запроса суммы подматрицы

Формула запроса суммы:

Детальный разбор элементов формулы:

— искомая сумма в прямоугольнике от до .

— сумма всего большого прямоугольника от до правого нижнего угла нашего целевого прямоугольника. Индексы увеличены на единицу из-за фиктивных нулей в префиксной матрице.

— площадь горизонтальной полосы, которая находится строго выше нашего целевого прямоугольника. Мы вычитаем ее.

— площадь вертикальной полосы, которая находится строго левее нашего целевого прямоугольника. Мы вычитаем и ее.

— площадь прямоугольника на пересечении двух отсеченных полос (слева-сверху).

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

Реализация функции запроса:

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

Разбор задачи: поиск оптимального квадрата

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

Без префиксных сумм мы бы написали четыре вложенных цикла. Два внешних перебирали бы левый верхний угол квадрата, а два внутренних — суммировали бы элементы внутри него. Временная сложность составила бы . При это операций, что гарантированно приведет к превышению лимита времени (Time Limit Exceeded) на платформе тестирования Яндекса.

Используя двумерные префиксные суммы, мы разбиваем задачу на два независимых этапа:

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

Поиск ответа: перебираем все возможные левые верхние углы квадрата размером . Для каждого угла запрашиваем сумму за . Обход займет .

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

В этом коде критически важно правильно определить границы циклов range(rows - K + 1). Ошибка на единицу (Off-by-one error) здесь приведет либо к пропуску последнего возможного квадрата, либо к выходу за границы матрицы. Если матрица имеет размер , а , то левый верхний угол может иметь индексы от до включительно (всего 3 варианта). Формула дает правильный аргумент для функции range().

Особенности работы с отрицательными числами и памятью

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

Однако главным ограничением структуры является пространственная сложность. Выделение памяти под дополнительную матрицу может стать проблемой при жестких ограничениях по памяти. В Python списки списков (list of lists) имеют значительный накладной расход памяти из-за того, что каждый вложенный список является отдельным объектом со своим заголовком, а внешний список хранит лишь ссылки на них.

Если в задаче требуется экстремальная экономия памяти, а исходная матрица больше не нужна для других операций, префиксные суммы можно строить in-place, прямо поверх исходной матрицы (сдвинув логику индексов и отказавшись от фиктивного нуля, что усложнит код ветвлениями if i > 0). Другой вариант оптимизации в Python — использование одномерного массива длиной с ручным вычислением плоских индексов , что избавляет от накладных расходов на объекты вложенных списков.

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

Разностный массив: техника массового обновления элементов на интервалах за O(1)

Система бронирования билетов на поезд получает тысячи запросов в секунду. Каждый запрос имеет формат: «добавить пассажиров на все станции от до ». Если маршрут состоит из 100 000 станций, а система должна обработать 100 000 таких запросов, наивный цикл, проходящий по массиву от до для каждого обновления, совершит в худшем случае операций. Это гарантированный Time Limit Exceeded на любой алгоритмической секции. Нам требуется структура, способная применять массовое обновление к целому отрезку за константное время , независимо от длины этого отрезка.

Анатомия разностного массива

В предыдущих материалах мы разобрали префиксные суммы — инструмент, который позволяет за узнавать сумму на любом отрезке, предварительно потратив времени на подготовку массива. Разностный массив (Difference Array) решает обратную задачу: он позволяет за изменять значения на любом отрезке, чтобы в самом конце за восстановить итоговый массив.

Если префиксная сумма — это алгоритмический аналог математического интеграла (накопления), то разностный массив — аналог производной (скорости изменения).

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

для всех

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

Механика обновления за константное время

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

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

Мы говорим: «начиная с индекса , значения увеличились на ». Для этого делаем .

Мы говорим: «начиная с индекса , это увеличение перестает действовать». Для этого делаем .

!Схема работы границ разностного массива

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

Эта операция требует ровно двух обращений к памяти, независимо от того, обновляем мы 5 элементов или 5 миллионов. Временная сложность одного запроса на обновление строго равна .

Управление памятью и выход за границы

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

Можно было бы добавить условие:

Однако ветвления (if-statement) внутри цикла обработки миллионов запросов замедляют работу процессора из-за сбросов конвейера предсказания ветвлений. Более элегантный и производительный паттерн — выделить для разностного массива память размером .

Если исходный массив имеет длину , мы создаем массив длины . Дополнительный элемент в самом конце служит «мусорной корзиной» (sink) для отрицательных компенсаций, когда . При восстановлении итогового массива мы просто игнорируем этот последний элемент, проходя префиксной суммой только до индекса . Это избавляет код от любых проверок границ и делает его линейным.

Практический разбор: бронирование мест

Рассмотрим классическую задачу на эту структуру. Дан массив из 5 нулей (станций). Поступают три запроса на добавление пассажиров:

Добавить 10 пассажиров на станции с 1 по 3.

Добавить 20 пассажиров на станции с 2 по 4.

Добавить 15 пассажиров на станции с 0 по 2.

Создаем разностный массив размером нулей:

Обрабатываем первый запрос: , , .

Текущее состояние : [0, 10, 0, 0, -10, 0]

Обрабатываем второй запрос: , , .

(здесь пригодился буферный элемент) Текущее состояние : [0, 10, 20, 0, -10, -20]

Обрабатываем третий запрос: , , .

Текущее состояние : [15, 10, 20, -15, -10, -20]

!Пошаговое применение запросов и восстановление массива

Фаза обновлений завершена. Теперь восстанавливаем итоговый массив путем вычисления префиксной суммы от массива (исключая последний буферный элемент).

- - - - -

Итоговый массив: [15, 25, 45, 30, 20]. Мы обработали все запросы за время , где — количество запросов, а — длина массива.

Программная реализация этого паттерна на Python выглядит лаконично:

Ограничения архитектуры Offline Processing

Важно понимать фундаментальное ограничение разностного массива: это структура для офлайн-обработки (offline processing). Это означает, что алгоритм строго разделен на две непересекающиеся фазы. Сначала мы должны получить и применить абсолютно все запросы на изменение. И только потом, один раз, мы запускаем фазу восстановления (префиксную сумму).

Если задача требует чередования операций — например, применить обновление, затем узнать значение конкретного элемента, затем снова применить обновление — разностный массив окажется неэффективным. Чтобы узнать точное значение после одного обновления, нам придется пересчитать префиксную сумму, что занимает времени. Если мы будем делать это после каждого запроса, общая сложность снова деградирует до .

Для задач с онлайн-запросами (когда чтения и записи чередуются) используются более сложные структуры данных, такие как Дерево отрезков (Segment Tree) или Дерево Фенвика (Fenwick Tree), которые обеспечивают время как для обновления отрезка, так и для запроса элемента. Разностный массив идеален только тогда, когда все изменения известны заранее или могут быть накоплены в пакет (batch) перед единственным чтением результата.

Переход к разреженным данным: сканирующая прямая

Во всех предыдущих примерах индексы и находились в пределах от до , где — разумное число, под которое можно выделить массив в оперативной памяти (например, до ). Но что если условие задачи меняется?

Предположим, и — это не индексы в массиве, а временные метки (timestamps) в миллисекундах или координаты на оси, которые могут достигать . Создавать массив diff = [0] (10*9 + 1) нельзя — это вызовет MemoryError, так как потребует гигабайты оперативной памяти, большая часть из которой будет заполнена нулями. Данные становятся разреженными (sparse).

Здесь на помощь приходит комбинация логики разностного массива и хеш-таблиц (словарей в Python). Вместо того чтобы хранить нули для индексов, где ничего не происходит, мы фиксируем только сами события изменения.

Логика и сохраняется полностью, но теперь — это не список, а словарь dict.

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

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

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