Префиксные суммы и счётчики

Пусть массив не меняется, но запросов много: для каждого полуинтервала [left, right) нужно быстро вернуть сумму его элементов. Для [3, -2, 5, 1] сумма [1, 4) равна -2 + 5 + 1 = 4.

Как отвечать на множество запросов диапазона

Дан массив длины n и q запросов с 0 <= left <= right <= n. Один и тот же элемент может входить во множество запросов. Сначала разрешена предобработка массива, после неё каждый ответ должен вычисляться быстро.

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

Для каждого запроса можно пройти от left до right - 1 и сложить элементы. Время равно сумме длин всех запросов, а в худшем случае — O(nq). Дополнительная память O(1), и для одного запроса это часто вполне разумное решение.

Почему перекрывающиеся запросы складывают одно и то же

При большом числе перекрывающихся запросов одинаковые префиксы массива складываются снова и снова. Например, запросы [0, 1000), [0, 1001) и [0, 1002) почти полностью повторяют одну работу.

Внутренний диапазон как разность накоплений

Заранее сохраним суммы от начала массива. Пусть prefix[i] — сумма первых i элементов, то есть диапазона [0, i). Тогда:

sum(left, right) = prefix[right] - prefix[left].

В prefix[right] есть и нужный диапазон, и элементы до left; вычитание prefix[left] убирает именно лишнюю начальную часть. Тот же приём строит префиксные счётчики: вместо значения добавляем 1, если элемент обладает нужным свойством, иначе 0.

Что хранится в prefix[i]

После обработки первых i элементов массив prefix содержит i + 1 значение, а prefix[i] в точности равен сумме values[0] + ... + values[i - 1]. База prefix[0] = 0 описывает сумму пустого префикса.

Переход prefix[i + 1] = prefix[i] + values[i] сохраняет этот инвариант.

Строим n + 1 накопленное значение

1. Создать prefix длины n + 1 и записать prefix[0] = 0.
2. Для каждого индекса i вычислить prefix[i + 1] = prefix[i] + values[i].
3. Для запроса проверить 0 <= left <= right <= n.
4. Вернуть prefix[right] - prefix[left].

Для подсчёта элементов по условию шаг 2 меняется на добавление нуля или единицы; формула запроса остаётся той же.

Построение и проверенный запрос полуинтервала

C++17

#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

std::vector<long long> buildPrefix(const std::vector<int>& values) {
    std::vector<long long> prefix(values.size() + 1, 0);

    for (std::size_t index = 0; index < values.size(); ++index) {
        prefix[index + 1] = prefix[index]
                          + static_cast<long long>(values[index]);
    }

    return prefix;
}

long long rangeSum(
    const std::vector<long long>& prefix,
    std::size_t left,
    std::size_t right
) {
    if (prefix.empty()) {
        throw std::invalid_argument("prefix must contain prefix[0]");
    }

    const std::size_t valueCount = prefix.size() - 1;
    if (left > right || right > valueCount) {
        throw std::out_of_range("expected 0 <= left <= right <= n");
    }

    return prefix[right] - prefix[left];
}

int main() {
    const std::vector<int> values{1, 2, 3};
    const std::vector<long long> prefix = buildPrefix(values);

    assert(rangeSum(prefix, 0, 3) == 6);
    assert(rangeSum(prefix, 1, 1) == 0);
    assert(rangeSum(prefix, 1, 3) == 5);
    std::cout << "OK\n";
}

Python 3

def build_prefix(values: list[int]) -> list[int]:
    prefix = [0]

    for value in values:
        prefix.append(prefix[-1] + value)

    return prefix


def range_sum(prefix: list[int], left: int, right: int) -> int:
    if not prefix:
        raise ValueError("prefix must contain prefix[0]")

    value_count = len(prefix) - 1
    if left < 0 or left > right or right > value_count:
        raise IndexError("expected 0 <= left <= right <= n")

    return prefix[right] - prefix[left]


values = [1, 2, 3]
prefix = build_prefix(values)

assert range_sum(prefix, 0, 3) == 6
assert range_sum(prefix, 1, 1) == 0
assert range_sum(prefix, 1, 3) == 5
print("OK")

Цена предобработки и одного запроса

Построение занимает O(n) времени и O(n) памяти. Каждый запрос использует два обращения и одно вычитание, то есть O(1). Для q запросов итог — O(n + q) времени.

Массив считается неизменяемым между построением и запросами. В C++ префиксы хранятся в long long; предполагается, что полная сумма помещается в этот тип. Python использует целые произвольной точности.

Пустые диапазоны, начало массива и неверные границы

• Пустой диапазон left == right: разность одного значения с самим собой равна нулю.
• left = 0: работает без отдельной ветки благодаря prefix[0] = 0.
• right = n: используется последний элемент массива префиксов.
• Пустой исходный массив: корректен только запрос [0, 0).
• Отрицательные элементы не мешают формуле.
• Неверный порядок или выход границы за n нужно отклонить до индексации.

Проверяем полный, пустой и внутренний диапазоны

Для [1, 2, 3] префиксы равны [0, 1, 3, 6]:

• [0, 3) → 6;
• [1, 1) → 0;
• [1, 3) → 5.

Дополнительно: для [-4, 10, -3] запрос [0, 2) должен вернуть 6, а для пустого массива [0, 0) — 0.

Когда много запросов оправдывают предобработку

Есть много запросов суммы или количества на диапазонах одного неизменяемого массива. Формулировки часто содержат «сколько на отрезке», «сумма от left до right» или «ответить на q запросов». Полуинтервалы особенно удобно выражаются разностью префиксов.

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

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

Зачем нужен дополнительный нулевой префикс

Вопрос. Зачем хранить n + 1 префикс, а не ровно n?

Ответ. Дополнительный prefix[0] = 0 представляет пустой префикс. Тогда сумма диапазона от самого начала равна той же общей формуле: prefix[right] - prefix[0], без обращения к индексу -1 и без отдельной ветки.

Как превратить сумму в счётчик признака

Вопрос. Как с помощью той же структуры считать положительные элементы на [left, right)?

Ответ. При построении нужно добавлять не само значение, а индикатор: 1, если values[i] > 0, иначе 0. Тогда каждый префикс хранит количество положительных элементов, а разность двух префиксов даёт их число в запросе.

Строим префиксный счётчик нулей

Задание. Постройте префиксный счётчик нулей для [0, 5, 0, 0, 7] и ответьте на запросы [0, 3) и [2, 5).

Подсказки. Начните с [0]. Для каждого элемента добавляйте к последнему счётчику 1, если элемент равен нулю, иначе 0. Получится zero_prefix = [0, 1, 1, 2, 3, 3].

Проверка. zero_prefix[3] - zero_prefix[0] = 2, а zero_prefix[5] - zero_prefix[2] = 2.

Самостоятельная задача о балансе диапазона

Задача 1

Дан неизменяемый массив целых чисел и список запросов [left, right). Для каждого запроса верните разность между количеством положительных и количеством отрицательных элементов диапазона; нули не учитываются. Отклоняйте неверные границы и оцените общую сложность для q запросов.

Нулевой префикс унифицирует все границы

Префикс сохраняет накопленный ответ для каждого начала [0, i). Поэтому любой внутренний диапазон получается вычитанием лишнего левого префикса; один раз заплатив O(n), мы отвечаем на каждый неизменяемый запрос за O(1).