Префиксные суммы: от 1D к 2D и подсчёту на прямоугольниках ТЕМА

О чём статья

Префиксные суммы — самая дешёвая по реализации техника на полосе сложности CF 1100–1700, и одна из самых частых. Идея сводится к одному переходу: вместо того чтобы на каждый запрос «сумма на отрезке» считать $O(n)$ операций, заранее накопить «сумму от начала до позиции $i$» — и тогда сумма любого отрезка считается за $O(1)$ через одно вычитание.

Эта статья — про базовый каркас и три типичных применения: одномерный шаблон, его двумерное обобщение через формулу включений-исключений, и более содержательный приём «prefix + hashmap», который даёт за $O(n)$ ответ на «сколько подотрезков имеют заданную сумму». Цель — довести шаблон до автоматизма, чтобы при виде слов «сумма на отрезке» или «подмножество подряд идущих элементов» рука сама тянулась за префиксным массивом, а ловушки на границах не съедали часов отладки.

---

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

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

• «Сумма $a_l + a_{l+1} + \ldots + a_r$» / «сумма в подпрямоугольнике». Прямой сигнал: одна цельная операция «суммирования по диапазону» — главный кандидат на префиксы.
• «Дано $q$ запросов вида …, выведи ответы». Если запросов много (сотни тысяч), а на каждый напрашивается $O(n)$ — общая сложность $O(nq)$ не помещается. Префиксы превращают её в $O(n + q)$.
• «Подсчитать, сколько подотрезков обладают свойством $X$». Свойство «сумма равна $K$», «сумма делится на $m$», «сумма больше $S$» — классические постановки под комбинацию prefix + hashmap или prefix + сортировка.
• Массив не изменяется. В условии нет «затем выполнить $u$ обновлений» или «измените $a_i$ на $v$». Если изменения есть — это сигнал к Fenwick / сегментному дереву, а не к префиксам.
• Аддитивная операция. Сумма, XOR, иногда количество чего-то конкретного. Если оператор — min / max / gcd, шаблон префиксов даёт ответы только для «диапазонов от начала», но не для произвольных $[l, r]$ — тут уже sparse table.

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

---

Базовый шаблон (1D)

Идея в одну фразу

Завести вспомогательный массив $P$ длины $n + 1$, где $P[i]$ — сумма первых $i$ элементов исходного массива. Тогда сумма любого отрезка $a[l..r]$ выражается через два значения этого массива.

Конвенция индексации

Пусть исходный массив $a$ длины $n$, индексы $0..n-1$. Префиксный массив $P$ длины $n + 1$: $P[0] = 0$, дальше каждое следующее значение — это предыдущее плюс соответствующий элемент массива. То есть $P[i]$ равно сумме первых $i$ элементов массива.

Тогда для отрезка $a[l..r]$ (оба конца включительно) сумма равна $P[r + 1] - P[l]$. Если в условии полуоткрытый сегмент (правый конец исключительно) — формула становится $P[r] - P[l]$. Это та же самая идея, просто без «$+1$» в индексе.

Важный совет: выбрать одну из двух конвенций (включительно или исключительно правый конец) и держаться её до конца задачи. Большая часть off-by-one в префиксных суммах рождается из перескока между этими двумя стилями в разных местах кода.

Псевдокод

прочитать массив 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)$ препроцессинг + $O(1)$ на запрос. На $q$ запросах — итог $O(n + q)$ против наивных $O(nq)$.

Почему шаблон работает

Сумма на отрезке — это разница двух «сумм от начала»: «всё до правого конца включительно» минус «всё до левого конца исключительно». Первое — это $P[r+1]$, второе — $P[l]$, отсюда $P[r+1] - P[l]$. Никакой «магии».

Тот же приём работает для любой операции, у которой есть обратная: XOR (обратная — снова XOR), сумма по простому модулю (обратная — вычитание по модулю). Для min / max обратной операции нет — поэтому шаблон префиксов на них не обобщается.

---

Задача-иллюстрация 1: суммы на отрезке (~CF 1100)

Условие

Дан массив целых чисел $a$ длины $n$ и $q$ запросов. Каждый запрос — пара $(l, r)$, $0 \le l \le r \le n - 1$. Нужно вывести сумму $a[l] + a[l+1] + \ldots + a[r]$.

Ограничения. $1 \le n, q \le 2 \cdot 10^5$, $|a_i| \le 10^9$. Гарантируется, что ответ умещается в 64-битное знаковое целое.

Формат ввода. В первой строке — $n$ и $q$. Во второй — $n$ чисел $a_0, \ldots, a_{n-1}$. Далее — $q$ строк по два числа $l, r$.

Формат вывода. $q$ строк — ответы на запросы в порядке их следования.

Пример. $a = [1, 3, -2, 4, 5]$, запрос $(1, 3)$. Ответ — $3 + (-2) + 4 = 5$.

Применение шаблона

База — стандартная:

$$P = [0, 1, 4, 2, 6, 11].$$

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

Запрос $(1, 3)$: $P[4] - P[1] = 6 - 1 = 5$. ✓

Код решения

Что поменялось

Ничего по сравнению с базовым шаблоном — задача один в один по идее. Это «нулевая» иллюстрация, фиксирующая шаблон в памяти. Дальше начинаются модификации.

---

Задача-иллюстрация 2: сумма в подпрямоугольнике (~CF 1400)

Условие

Дана сетка $n \times m$ целых чисел $a[i][j]$, $0 \le i < n$, $0 \le j < m$. На каждый из $q$ запросов — четвёрка $(r_1, c_1, r_2, c_2)$, $0 \le r_1 \le r_2 < n$, $0 \le c_1 \le c_2 < m$. Нужно вывести сумму всех элементов в подпрямоугольнике с углами $(r_1, c_1)$ и $(r_2, c_2)$ включительно.

Ограничения. $1 \le n, m \le 10^3$, $1 \le q \le 2 \cdot 10^5$, $|a[i][j]| \le 10^9$.

Пример. Сетка $3 \times 3$:

1 2 3
4 5 6
7 8 9

Запрос $(0, 0, 1, 1)$: подпрямоугольник 1 2 / 4 5, сумма $1 + 2 + 4 + 5 = 12$.

Применение шаблона

Двумерный аналог префиксного массива: $P[i][j]$ — это сумма всех элементов в верхне-левом подпрямоугольнике, у которого правый нижний угол находится перед клеткой $(i, j)$ (то есть включает строки $0..i-1$ и столбцы $0..j-1$). Размер $P$ — $(n + 1) \times (m + 1)$; нулевая строка и нулевой столбец заполнены нулями — это база, которая снимет с формул проверки на края.

Заполнение идёт по принципу «сложить две половины и вычесть пересечение». Чтобы посчитать $P[i+1][j+1]$ (то есть сумму подпрямоугольника, включающего всё слева-сверху и плюс саму клетку $a[i][j]$), складываем:

• сумму «верхней половины» $P[i][j+1]$ — всё, что выше текущей строки;
• сумму «левой половины» $P[i+1][j]$ — всё, что левее текущего столбца;
• сам элемент $a[i][j]$.

Но «верхняя половина» и «левая половина» пересекаются по верхне-левому подпрямоугольнику $P[i][j]$ — его учли дважды, поэтому вычитаем один раз. В коде это одно выражение P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + a[i][j].

Запрос «сумма в подпрямоугольнике от $(r_1, c_1)$ до $(r_2, c_2)$ включительно» — та же логика, в обратную сторону. Берём «полный подпрямоугольник от $(0, 0)$ до $(r_2, c_2)$» — это $P[r_2+1][c_2+1]$. Из него вычитаем верхнюю полосу (всё, что выше $r_1$) и левую полосу (всё, что левее $c_1$). Эти полосы пересекаются по верхне-левому подпрямоугольнику $P[r_1][c_1]$ — он вычтен дважды, прибавляем обратно. В коде:

S = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

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

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

$n = m = 3$, сетка как выше.

Префиксная матрица $P$ размера $4 \times 4$ (нулевая строка / столбец — нули):

Проверка $P[2][2] = P[1][2] + P[2][1] - P[1][1] + a[1][1] = 3 + 5 - 1 + 5 = 12$. ✓

Запрос $(0, 0, 1, 1)$: $S = P[2][2] - P[0][2] - P[2][0] + P[0][0] = 12 - 0 - 0 + 0 = 12$. ✓

Запрос $(1, 1, 2, 2)$ (подпрямоугольник 5 6 / 8 9, сумма $5 + 6 + 8 + 9 = 28$): $S = P[3][3] - P[1][3] - P[3][1] + P[1][1] = 45 - 6 - 12 + 1 = 28$. ✓

Код решения

Что поменялось

• Размерность состояния выросла на единицу. Теперь префиксный массив двумерный, рекуррент содержит три слагаемых.
• Запрос — четыре обращения вместо двух. Включения-исключения дают плюс-минус-минус-плюс. Самый частый источник WA — перепутанные знаки.
• Память. $(n+1) \times (m+1)$ длинных целых при $n = m = 1000$ — около 4 МБ в C++ (long long), в Python — ощутимо больше (~30–60 МБ). Если упирается в лимит памяти, можно переиспользовать строку «над текущей», сэкономив до $O(m)$ памяти, но ценой потери возможности отвечать на запросы после прохода — для постзапросов нужна вся матрица.
• Конвенция индексации одна. $P$ имеет «лишнюю» нулевую строку и нулевой столбец — это убирает все проверки «а если $r_1 = 0$» из формулы запроса. Альтернатива — хранить $P$ размера $n \times m$ и явно проверять края — даёт ту же сложность, но больше места для ошибок на границах.

---

Задача-иллюстрация 3: подсчёт подотрезков с суммой = K (~CF 1500)

Условие

Дан массив $a$ длины $n$ и целое число $K$. Найти количество подотрезков (непустых, подряд идущих подпоследовательностей) $a[l..r]$, сумма которых равна ровно $K$.

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

Пример. $a = [1, 1, 1]$, $K = 2$. Ответ — 2 (подотрезки $a[0..1]$ и $a[1..2]$).

Пример 2. $a = [3, 4, 7, 2, -3, 1, 4, 2]$, $K = 7$. Ответ — 4: $[7]$, $[3, 4]$, $[7, 2, -3, 1]$, $[1, 4, 2]$. (Считаем руками, чтобы потом сверить с программой.)

Идея

Перейдём к префиксным суммам с обычной конвенцией $P[r+1] - P[l]$ для суммы $a[l..r]$. Зафиксируем правый конец подотрезка — какой-то $r$. Условие «сумма равна $K$» означает, что нам нужен такой $l$, чтобы $P[l] = P[r+1] - K$ — то есть конкретное число, которое мы можем заранее посчитать.

И вопрос превращается в «сколько раз это конкретное значение встретилось среди уже виденных префиксов $P[0], P[1], \ldots, P[r]$?» — типичный сценарий для хеш-таблицы, где мы храним «значение префикса → сколько раз встречалось».

Алгоритм

1. Завести счётчик cnt (хеш-таблица «значение → количество вхождений»).
2. Положить в счётчик cnt[0] = 1 — это соответствует $P[0]$, пустому префиксу.
3. Идти по $r$ от $0$ до $n - 1$, поддерживая текущее значение $P[r+1]$ инкрементально. На каждом шаге:
   • Прибавить к ответу cnt.get(P[r+1] - K, 0) — это количество подотрезков, заканчивающихся в позиции $r$ и имеющих сумму $K$.
   • Увеличить cnt[P[r+1]] на 1.

Сложность: $O(n)$ времени (если хеш-таблица работает за $O(1)$ в среднем) и $O(n)$ памяти.

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

Возьмём второй пример: $a = [3, 4, 7, 2, -3, 1, 4, 2]$, $K = 7$.

Сначала $cnt = \{0: 1\}$, ответ = 0, $P_{\text{cur}} = 0$.

Ответ — 4, совпадает с подсчётом руками. ✓

Код решения

Что поменялось

• От запроса к подсчёту. Префиксы здесь не отвечают на «сумма $a[l..r]$», а помогают за один проход найти число пар $(l, r)$ с заданной суммой.
• Хеш-таблица как универсальный счётчик. Значения префиксных сумм могут быть любыми (включая отрицательные и большие); массив-счётчик не подойдёт, нужна именно хеш-таблица.
• Порядок «сначала прибавить, потом записать». Это критично: если записать $P_{\text{cur}}$ в cnt до прибавления к ответу, мы засчитаем сам $P_{\text{cur}}$ — но подотрезок $a[\ldots r]$ с суммой $K$ должен соответствовать $l < r + 1$, то есть строго раньше. Поменяв порядок, при $K = 0$ и нулевых элементах получим переучёт.
• Инициализация cnt[0] = 1. Это считает «пустой префикс» — соответствует подотрезку, начинающемуся с самого первого элемента и имеющему сумму $K$. Без этой строки потеряется часть ответа.

---

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

1. Off-by-one в индексации. Самая массовая категория ошибок. Лечится одной мерой: с самого начала зафиксировать конвенцию ($P[i]$ — сумма первых $i$ элементов, индексы $P$ от $0$ до $n$) и не отступать. Перевод запроса $(l, r)$ — включительно — в $P[r+1] - P[l]$, и больше не задумываться.
2. Перепутанные знаки в 2D inclusion-exclusion. Формула «плюс — минус — минус — плюс» легко пишется на автомате с ошибкой («минус — плюс — плюс — минус»). Проверка — на маленьком примере 2×2 или 3×3 вручную, как в разборе выше: одна несовпавшая клетка ловит ошибку до отправки.
3. Переполнение в C++. $n$ слагаемых до $10^9$ дают сумму до $10^{14}$ — это ещё в long long, но если возводить в квадрат или умножать — нужен __int128 или модульная арифметика. В Python целочисленных переполнений нет, поэтому язык прощает эту ошибку.
4. Хеш-атака на unordered_map в C++. Дефолтный хеш std::hash<long long> уязвим к специально подобранным входам и может деградировать до $O(n^2)$. На Codeforces регулярно встречаются «анти-хеш» тесты. Решение — кастомный хеш (Splitmix64-подобный) или __gnu_pbds::gp_hash_table. В Python dict использует рандомизированный seed, но на массовом ключе типа целых чисел — этот класс атак реже выживает на 2 секундах TL.
5. Префиксы для не-аддитивной операции. Попытка построить «префиксный минимум» и ответить на «минимум на $[l, r]$» через $\min(P_{\min}[r], P_{\min}[l-1])$ — одна из самых частых ошибок начинающих. У min нет обратной операции, и формула не работает: для произвольного отрезка нужен sparse table или сегментное дерево.
6. Забыть cnt[0] = 1 в задаче «сумма = K». Без этой строки теряется случай, когда подходящий подотрезок начинается с $a[0]$ — половина или треть ответа уходит в минус.
7. Переполнение ответа. Количество подотрезков — до $n(n+1)/2 = 2 \cdot 10^{10}$ при $n = 2 \cdot 10^5$. В C++ счётчик ответа должен быть long long. В Python — без забот.

---

Когда префиксы НЕ подходят

Несколько случаев, когда шаблон с виду применим, а на деле нет.

• Массив изменяется между запросами. После каждого update пришлось бы пересчитывать $P$ за $O(n)$, и общая сложность $O(nu + q)$ при больших $u$ непригодна. Здесь нужны Fenwick (BIT) или сегментное дерево: они дают $O(\log n)$ и на запрос, и на обновление.
• Запрос — не аддитивная операция. Min, max, gcd на отрезке, число различных элементов — стандартный шаблон префиксов не работает (нет обратимости). Sparse table — для idempotent-операций (min/max/gcd) на статичном массиве, отвечает за $O(1)$. Сегментное дерево — для всех операций, но за $O(\log n)$.
• Запрос требует подмножество, не подсегмент. Если выбираются произвольные элементы (не подряд идущие) — прямой шаблон префиксов не применим. Здесь часто помогают сортировка, биткарта или совсем другая структура.
• Ограничения на суммы по «окну фиксированной ширины». Технически префиксы работают, но эффективнее скользящее окно с двумя указателями — $O(n)$ без аллокации $O(n)$ памяти под массив $P$.

Полезное правило: если в условии есть слова «обновить $a[i]$» — забыть про префиксы и сразу начинать с Fenwick.

---

Связанные техники

• Difference array (массив разностей) — обратная сторона префиксов. Помогает применить $u$ обновлений вида «прибавить $\Delta$ на отрезке $[l, r]$» за $O(u + n)$ суммарно: каждое обновление — два точечных изменения в массиве разностей, в конце один проход с накоплением даёт итоговый массив.
• Скользящее окно (sliding window) и два указателя. Когда границы окна монотонно «едут» по массиву, два указателя дают $O(n)$ без явного префиксного массива. Префиксы — более универсальный инструмент, скользящее окно — более экономный по памяти и часто более идиоматичный для конкретных задач.
• DP с префиксными суммами. Часто переход в DP вида $f[i] = \min(f[j] + \text{сумма } a[j+1..i])$ удаётся ускорить с $O(n^2)$ до $O(n)$ или $O(n \log n)$, если подставить «сумму $a[j+1..i] = P[i] - P[j]$» и заметить, что задача сводится к «минимуму $f[j] - P[j]$ на префиксе» — тогда поддерживается одной переменной.
• Fenwick (BIT) и сегментное дерево. Когда массив изменяется. Ответ за $O(\log n)$, обновление за $O(\log n)$, общая сложность $O((n + q + u) \log n)$.

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

---

Итого

• Техника: $P[0] = 0$, $P[i] = a[0] + \ldots + a[i-1]$. Сумма $a[l..r] = P[r+1] - P[l]$.
• Сложность: $O(n)$ препроцессинг + $O(1)$ на запрос. На $q$ запросах — $O(n + q)$.
• 2D: $P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + a[i][j]$, ответ на запрос — формула включений-исключений из четырёх членов.
• Сигналы в условии: «сумма на отрезке/в подматрице», «много запросов», «массив фиксирован», «подсчитать подотрезки с суммой = K».
• Типичные ловушки: off-by-one на границах, знаки в 2D, переполнение в C++, забытая инициализация cnt[0] = 1 в counting-варианте, попытка распространить шаблон на min/max.
• Когда не подходит: массив изменяется (Fenwick/сегментное дерево), не-аддитивная операция (sparse table), произвольное подмножество вместо подсегмента.