Префиксные суммы и разностный массив

Задача: много раз спросить сумму на отрезке массива. В лоб это $O(n)$ на запрос. Приём, который сводит его к константе, простой до неприличия — и именно поэтому его стоит разобрать до конца, вместе с зеркальным близнецом.

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

Заведём массив, где в ячейке $i$ лежит сумма первых $i$ элементов:

vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];

long long sum(int l, int r) { return prefix[r + 1] - prefix[l]; }   // [l, r]

Лишняя ячейка в начале — не эстетика. Без неё пришлось бы отдельно обрабатывать случай $l = 0$, и в коде появился бы if, который однажды забудут.

Тип суммы почти всегда должен быть шире типа элементов: сто тысяч чисел до миллиарда дают $10^{14}$, а это уже не int.

Разностный массив

Обратная задача: много раз прибавить число на отрезке, а сам массив нужен только в конце.

vector<long long> diff(n + 2, 0);

void add(int l, int r, long long value) {   // прибавить на [l, r]
    diff[l] += value;
    diff[r + 1] -= value;
}

// в конце — один проход с накоплением
long long running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; a[i] += running; }

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

Главное правило

Одно превращается в другое префиксным суммированием, и отсюда ограничение, которое надо помнить:

• префиксные суммы нельзя обновлять по ходу — изменение одного элемента портит все префиксы правее;
• разностный массив нельзя опрашивать по ходу — пока не просуммировали, значений там нет.

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

Проверять это стоит по условию: если все запросы даны сразу, а ответ печатается в конце — приём подходит. Если запросы идут вперемешку с изменениями — нет.

Приём накладывается сам на себя

Бывает, что прибавление идёт не к массиву, а к операциям над массивом. Скажем: есть $m$ операций «прибавить $d$ на отрезке», и есть $k$ запросов «применить операции с $x$-й по $y$-ю».

Прямое применение стоило бы $k \cdot m \cdot n$. Но здесь два уровня одного и того же приёма:

1. Первым разностным массивом считаем, сколько раз применена каждая операция.
2. Вторым — сколько прибавлено к каждому элементу, где вклад операции умножен на число её применений.

Получается $k + m + n$. Величины при этом растут: сто тысяч применений по сто тысяч единиц на сто тысяч операций дают $10^{15}$, и 32 бита кончаются задолго до этого.

Два измерения

Сумма по прямоугольнику собирается включением-исключением из четырёх префиксов:

prefix[r][c] = a[r][c] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1];

// сумма по прямоугольнику [r1..r2] × [c1..c2]
sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1];

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

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