Стратегия победы: префиксные суммы — от 1D к 2D и подсчёту на подотрезках СТРАТЕГИЯ

О чём эта статья

Серия «Стратегия победы» — про траекторию тренировки, а не про одну задачу. Берём одну технику и проходим её на трёх уровнях нарастающей сложности, явно фиксируя, что именно усложняется между ступенями. Тема этой статьи — префиксные суммы, одна из самых дешёвых по реализации и самых частых на полосах CF 1100–2000.

Большинство участников осваивает базовый шаблон префиксных сумм быстро — за пару задач. Сложнее становится, когда задача требует двумерных префиксов (с inclusion-exclusion) или когда префиксы становятся не самоцелью, а инструментом подсчёта — как в задачах «сколько подотрезков обладают свойством $X$». Эта статья показывает путь от базового шаблона к этому уровню применения, шаг за шагом.

---

Ядро техники

Префиксная сумма — это вспомогательный массив, в котором каждый элемент хранит сумму всех элементов исходного массива от начала до текущей позиции. Имея такой массив, ответ на любой запрос «сумма на отрезке $[l, r]$» считается за одно вычитание: $P[r + 1] - P[l]$. Препроцессинг — $O(n)$, каждый запрос — $O(1)$.

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

Базовый шаблон (псевдокод)

прочитать массив a длины n
P[0] ← 0
для i от 0 до n-1:
    P[i+1] ← P[i] + a[i]

на каждый запрос (l, r):     // a[l..r] включительно
    ответ ← P[r+1] - P[l]

Сложность базового шаблона: $O(n + q)$ время, $O(n)$ память.

Что мы будем усложнять по мере роста:

• Ступень 1 → ступень 2: одномерный массив превращается в двумерную сетку; одно вычитание заменяется на четыре с учётом формулы включений-исключений.
• Ступень 2 → ступень 3: вместо «считать сумму на отрезке» приходит обратная задача: «по какому свойству префиксной суммы найти пары $(l, r)$, чтобы отрезок имел нужное свойство». Здесь префикс соединяется с хешмапом.

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

---

Ступень 1 — CF ~1200 (одномерный шаблон, запросы на отрезке)

Условие

Дан массив $a_1, a_2, \ldots, a_n$ из целых чисел. Поступает $q$ запросов; каждый запрос — пара $(l, r)$, $1 \le l \le r \le n$. На каждый запрос нужно вывести сумму $a_l + a_{l+1} + \cdots + a_r$.

Ограничения. $1 \le n, q \le 10^5$, $|a_i| \le 10^9$.

Как применяется базовый шаблон

Лобовое решение — для каждого запроса пройти от $l$ до $r$ и просуммировать. Это $O(nq) = 10^{10}$ операций. Не помещается.

Заведём префиксный массив $P$ длины $n + 1$ с конвенцией $P[0] = 0$, $P[i] = a_1 + a_2 + \cdots + a_i$. Тогда сумма на отрезке $[l, r]$ — это $P[r] - P[l - 1]$ (если индексация массива $a$ с единицы, как в условии). Препроцессинг — $O(n)$, каждый запрос — $O(1)$.

Разбор на примере

$n = 5$, $a = [3, -1, 4, 1, 5]$. Префиксы:

Запросы:

• $(2, 4)$: $P[4] - P[1] = 7 - 3 = 4$. Проверка: $-1 + 4 + 1 = 4$ ✓
• $(1, 5)$: $P[5] - P[0] = 12 - 0 = 12$. Проверка: $3 - 1 + 4 + 1 + 5 = 12$ ✓
• $(3, 3)$: $P[3] - P[2] = 6 - 2 = 4$. Проверка: $a_3 = 4$ ✓

Код решения

Сложность: $O(n + q)$.

Что закрыли

На этом уровне закрыли сам шаблон 1D-префиксов: индексацию с единицы или нуля, базовую формулу $P[r] - P[l - 1]$. На следующей ступени к одной оси добавится вторая, и одно вычитание расщепится на четыре.

---

Ступень 2 — CF ~1600 (двумерные префиксы и inclusion-exclusion)

Условие

Дана прямоугольная сетка $n \times m$ с целыми числами $a_{i, j}$. Поступает $q$ запросов; каждый запрос — четвёрка $(r_1, c_1, r_2, c_2)$, $1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$. На каждый запрос нужно вывести сумму чисел в подпрямоугольнике с верхним левым углом $(r_1, c_1)$ и нижним правым $(r_2, c_2)$ включительно.

Ограничения. $1 \le n, m \le 1000$, $1 \le q \le 10^5$, $|a_{i, j}| \le 10^9$.

Что меняется в шаблоне

• Состояние: было одно — индекс $i$. Стало два — пара $(i, j)$.
• Препроцессинг: было $P[i + 1] = P[i] + a_i$. Стало $$P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a[i][j].$$ Формула — прямое применение принципа включений-исключений: «прямоугольник от $(0, 0)$ до $(i, j)$ = верхняя полоса + левая полоса − дважды посчитанный квадрат + текущая клетка».
• Запрос: было $P[r] - P[l - 1]$. Стало $$\text{ответ} = P[r_2][c_2] - P[r_1 - 1][c_2] - P[r_2][c_1 - 1] + P[r_1 - 1][c_1 - 1].$$ Четыре слагаемых с чередованием знаков — те же включения-исключения, но в обратном направлении.

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

Разбор на примере

Сетка $3 \times 3$:

1 2 3
4 5 6
7 8 9

Префиксы $P[i][j]$ (с $P[0][\cdot] = P[\cdot][0] = 0$):

Запрос $(2, 2, 3, 3)$: подпрямоугольник со значениями $5, 6, 8, 9$, сумма $28$.

По формуле:

$$P[3][3] - P[1][3] - P[3][1] + P[1][1] = 45 - 6 - 12 + 1 = 28.$$

Совпадает.

Код решения

Сложность: $O(n \cdot m + q)$. Память $O(n \cdot m)$ — при $n = m = 1000$ это $10^6$ long long, около $8$ МБ.

Что закрыли

Ступень 2 — умение расширить шаблон на $k$ осей. На двух осях получаем четыре слагаемых; на трёх (если когда-то понадобятся 3D-префиксы для подсчёта в объёме) — восемь, с тем же чередованием знаков. Это inclusion-exclusion в чистом виде: коэффициенты $(-1)^{|S|}$ по подмножеству $S$ «выбранных осей».

Следующий шаг — выйти за рамки прямых диапазонных запросов. Префиксы становятся инструментом подсчёта: задача формулируется как «сколько отрезков обладают свойством $X$», и префиксная сумма из вспомогательного массива превращается в ключ структуры данных.

---

Ступень 3 — CF ~2000 (prefix + hashmap, подсчёт подотрезков с заданной суммой)

Условие

Дан массив целых чисел $a_1, a_2, \ldots, a_n$ и целое число $K$. Найти количество подотрезков массива (непрерывных подмассивов $a_l, a_{l+1}, \ldots, a_r$), у которых сумма равна ровно $K$.

Ограничения. $1 \le n \le 2 \cdot 10^5$, $|a_i|, |K| \le 10^9$.

Что меняется в шаблоне

• Структура данных: двумерного массива больше нет. Префиксы остались одномерные, но теперь они ключи хешмапа, а не индексы для прямого доступа.
• Интеграция с другой техникой: соединяются префиксные суммы и хеш-таблица. Свойство «сумма отрезка $[l, r]$ равна $K$» переписывается как «$P[r] - P[l - 1] = K$», то есть «пара префиксов с разностью $K$». Подсчёт пар префиксов с заданной разностью — стандартная задача на хешмап: для каждого правого конца $P[r]$ проверяем, сколько раз раньше встречалось значение $P[r] - K$.
• Доказательство: соответствие подотрезков и пар префиксов биективное. Каждый подотрезок $[l, r]$ задаёт пару $(P[l - 1], P[r])$, и наоборот, каждая пара $(P[i], P[j])$ с $i < j$ задаёт подотрезок $[i + 1, j]$. Поэтому подсчёт пар префиксов с разностью $K$ — это то же самое, что подсчёт подотрезков с суммой $K$.

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

Разбор на примере

$n = 5$, $a = [2, -1, 3, 1, -1]$, $K = 3$. Префиксы (с $P[0] = 0$): $0, 2, 1, 4, 5, 4$.

Идём слева направо. Для каждой позиции $r$ ищем, сколько раз раньше встречалось $P[r] - K$.

После каждого шага увеличиваем счётчик для $P[r]$ в хешмапе. Важно: в начале мы кладём в хешмап одну запись $\{0: 1\}$, чтобы корректно обрабатывались отрезки, начинающиеся с первого элемента (когда $l = 1$, разность с $P[l - 1] = P[0] = 0$).

Ответ — $3$. Проверка ручным перебором подотрезков с суммой $3$:

• $[2, -1, 3, 1, -1]$ — позиции $1..5$, сумма $4$. Нет.
• $[-1, 3, 1]$ — позиции $2..4$, сумма $3$. Да.
• $[3]$ — позиция $3$, сумма $3$. Да.
• $[3, 1, -1]$ — позиции $3..5$, сумма $3$. Да.

Три подотрезка, ответ совпадает.

Код решения

Сложность: $O(n)$ в среднем (с учётом операций хеш-таблицы). Память: $O(n)$ под хешмап.

Что закрыли

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

• «Сумма равна $K$» → $P[r] - P[l - 1] = K$ → пары префиксов с разностью $K$.
• «Сумма делится на $m$» → $P[r] \equiv P[l - 1] \pmod m$ → пары префиксов с одинаковым остатком.
• «Сумма $\ge K$» при положительных значениях → отсортированные префиксы + бинпоиск или two pointers.
• «XOR-сумма равна $K$» → пары префиксов с XOR равным $K$ → хешмап по XOR-префиксам.

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

---

Что нужно держать в голове при переходе между ступенями

Эта таблица — «карта местности» для тренировки. Её имеет смысл держать под рукой в первые $2$–$3$ недели прохождения этой полосы. Любую задачу на префиксы можно отнести к одной из трёх категорий, и шаблон применять соответствующий.

---

Типичные ловушки на каждой ступени

• Ступень 1: путаница «включающий» и «полу-открытый» правый конец. В одной строке кода P[r + 1] - P[l] (правый конец включительно), в другой — P[r] - P[l] (правый конец исключительно). Симптом — off-by-one на коротких отрезках. Лекарство — одна конвенция на всю задачу.
• Ступень 2: путаница строк и столбцов. Формула с четырьмя слагаемыми требует строгого порядка осей. Если перепутать $(i - 1, j)$ и $(i, j - 1)$, на симметричных примерах решение «случайно» проходит, на несимметричных — WA. Лекарство — рисовать формулу на бумаге перед написанием кода.
• Ступень 3: забытая cnt[0] = 1. Если не учесть «пустой префикс» в начале, потеряем подотрезки, начинающиеся с первого элемента. Симптом — ответ меньше эталона ровно на число таких подотрезков. Лекарство — выработать рефлекс: первая строка после объявления хешмапа — увеличить счётчик для нулевого префикса.
• Ступень 3: unordered_map против анти-хеш-атак. На Codeforces бывают тесты, специально сконструированные против unordered_map<long long, ...> со стандартным хешем. Лекарство — кастомный хеш с рандомным сидом или map<long long, ...> (логарифмический, иногда чуть быстрее на адверсариальных тестах).
• Все ступени: int под суммы. $n = 10^5$, $|a_i| = 10^9$ — сумма до $10^{14}$, int переполнится. long long в C++ обязателен, в Python автоматически.

---

План тренировки

Практический чек-лист:

1. Решить ступень 1 самостоятельно (без подсмотра кода). Цель — отработать индексацию и формулу $P[r] - P[l - 1]$ до автоматизма.
2. Решить $3$–$5$ задач полосы CF ~$1200$ на одномерные префиксы. На Codeforces можно искать по тегу dp + сложности $1100$–$1300$, фильтровать по формулировкам «сумма на отрезке», «диапазонный запрос».
3. Перейти к ступени 2. Если застреваем более $30$ минут — открыть разбор в этой статье. После — самостоятельно реализовать без подсмотра.
4. После ступени 2 — $3$–$5$ задач полосы CF ~$1500$–$1600$ на двумерные префиксы. Часто формулируются как «максимальная сумма прямоугольника» (это уже Kadane 2D, но шаг построения префиксов в нём — обязательный).
5. Ступень 3 — аналогично, но без жёсткого ограничения по времени. Это полоса CF ~$1800$–$2000$, разбираться имеет смысл медленно. Лучший способ закрепить — переформулировать самостоятельно несколько задач с других тегов («подсчёт подотрезков», «подсчёт пар индексов») через язык «префикс + хешмап» и убедиться, что схема ложится.
6. Финал тренировки — попытаться решить смесь: задача, где одна часть — двумерные префиксы, другая — подсчёт через хешмап. Такие гибриды появляются в полосе CF ~$2200$+ и тренируют не саму технику, а переключение между ступенями внутри одной задачи.

---

Итого

• Тема: префиксные суммы — от диапазонных запросов к подсчёту подотрезков.
• Траектория: CF ~$1200$ → ~$1600$ → ~$2000$, с усложнением: одна ось → две оси (inclusion-exclusion) → префикс как ключ хешмапа.
• Ключевое умение: не просто знание формулы $P[r] - P[l - 1]$, а способность переформулировать задачу через язык префиксов: видеть «подотрезок с суммой $K$» как «пара префиксов с разностью $K$», «подматрица с суммой $K$» как «четыре префикса, связанные формулой включений-исключений», и так далее.