Сумма любого диапазона вычитанием

Построение префиксного массива было подготовительным этапом. Теперь начинается самое интересное: вычисление суммы любого отрезка с помощью одного вычитания. ⚡

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

Чтобы просуммировать элементы от l до r, вычтите prefix[l] из prefix[r + 1]. Эта единственная формула работает для любого диапазона.

В prefix[r + 1] содержатся все элементы до r включительно, а в prefix[l] — все элементы до l. Разность оставляет ровно средний срез.

Для [3, 1, 4] массив префиксных сумм равен [0, 3, 4, 8]. Чтобы просуммировать индексы от 1 до 2, вычислите 8 минус 3 и получите 5. Это совпадает с 1 плюс 4.

Каждый запрос — это всего одно вычитание, поэтому он выполняется за O(1). Тысяча запросов требует столько же времени на один запрос, сколько и один запрос.

Самая распространённая ошибка — неправильный индекс на правой границе. При начальном нуле всегда используйте prefix[r + 1], а не prefix[r]. Не забудьте проверить эту границу.

Заранее решите, входит ли r в диапазон. Эта формула рассматривает диапазон как включающий и l, и r, чего обычно ожидают задачи на соревнованиях.

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

Чтобы просуммировать весь массив, выполните query, где l равно 0, а r равно n минус 1. Формула даст prefix[n] — общую сумму.

Когда задача содержит много вопросов о сумме на диапазоне одного и того же массива, префиксные суммы превращают цикл за O(n) для каждого запроса в мгновенные ответы.

Теперь Вы умеете находить сумму любого диапазона за O(1), вычитая prefix[l] из prefix[r + 1]. Учитывайте смещение из-за начального нуля — и ошибок не будет. ✅