Скользящее окно и префиксные суммы

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

Когда задача про непрерывный подотрезок (подстроку, окно фиксированной или переменнойИменованное хранилище для значения. Имя связывается со значением через присваивание: x = 5. длины), наивное решение перебирает все подотрезки — O(n²). Скользящее окно держит «рамку» [left, right] и двигает её правый край, добавляя новый элемент, а левый — когда нужно сжать окно. Каждый элемент входит и выходит из окна один раз → O(n).

Ключевой трюк: при сдвиге окна не пересчитываем сумму заново, а корректируем — прибавляем вошедший элемент и вычитаем вышедший. Это превращает O(n·k) в O(n).

Окно переменной длины

Иногда длина окна не фиксирована: нужно найти, например, самую длинную подстроку без повторов. Тогда правый край расширяет окно, а левый догоняет, когда возникает нарушение условия (повтор). Помогает множествоКоллекция уникальных элементов без порядка: {1, 2, 3}. По-английски set. set для быстрой проверки.

Префиксные суммы

Префиксная сумма — массив, где prefix[i] хранит сумму всех элементов до позиции i. Имея его, сумму любого подотрезка [l, r] можно получить за O(1): prefix[r+1] − prefix[l]. Это незаменимо, когда сумм на подотрезках нужно много.

Вернётся 8 (3 + 1 + 4). Формула prefix[3] − prefix[0] = 8 − 0. Один раз построив префиксный массив за O(n), мы отвечаем на любой запрос суммы мгновенно.

⚠️ Частые ошибки новичков

Ошибка. Перепутать границы в префиксных суммах и написать prefix[r] − prefix[l] вместо prefix[r+1] − prefix[l]. Префиксный массив сдвинут на единицу (начинается с нуля), поэтому правую границу берут с +1. Запустите код и сравните неверный результат с правильным.