Разбор задачи «Суммы на отрезках»

1. Идея

Каждый запрос просит сумму на отрезке [l, r]. Если считать её наивно, каждый запрос стоит O(n), и при большом числе запросов это слишком медленно. Спасают префиксные суммы: один раз посчитав их за O(n), дальше на каждый запрос отвечаем за O(1).

2. Наблюдения

Введём массив pref, где pref[i] — сумма первых i элементов: pref[0] = 0, pref[i] = pref[i-1] + a[i]. Тогда сумма на отрезке [l, r] равна pref[r] - pref[l-1]: из суммы до r вычитаем сумму до l-1, остаётся ровно то, что лежит на позициях от l до r.

3. Алгоритм

1. Считать n и массив.
2. Построить префиксные суммы pref за один проход.
3. Для каждого запроса l, r вывести pref[r] - pref[l-1].

4. Почему это работает

pref[r] учитывает элементы с позиций 1..r, pref[l-1] — элементы 1..l-1. Их разность оставляет только позиции l..r, что и есть искомая сумма.

5. Сложность

Предподсчёт — O(n), каждый запрос — O(1). Итого O(n + q) по времени и O(n) по памяти. Суммы могут выходить за 32-битный тип, поэтому используем 64-битные числа.

Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }

    return 0;
}

Код на Python 3

n = int(input())
a = list(map(int, input().split()))

pref = [0] * (n + 1)
for i in range(1, n + 1):
    pref[i] = pref[i - 1] + a[i - 1]

q = int(input())
res = []
for _ in range(q):
    l, r = map(int, input().split())
    res.append(str(pref[r] - pref[l - 1]))
print("\n".join(res))