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

1. Идея

Нужно много раз находить сумму на подотрезке массива: от l до r.

Если для каждого запроса просто складывать элементы от l до r, то один запрос может работать за O(n), а все запросы — за O(nq). При n, q до 2 * 10^5 это слишком медленно.

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

Для этого используются префиксные суммы.

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

Определим массив pref, где:

• pref[0] = 0
• pref[i] — сумма первых i элементов массива

То есть:

• pref[1] = a[1]
• pref[2] = a[1] + a[2]
• ...
• pref[i] = a[1] + a[2] + ... + a[i]

Тогда сумма на отрезке [l, r] равна:

pref[r] - pref[l - 1]

Почему это так:

• pref[r] содержит сумму от 1 до r
• pref[l - 1] содержит сумму от 1 до l - 1
• если вычесть второе из первого, останется сумма от l до r

Это и есть основной приём задачи.

3. Алгоритм

1. Считываем n и q.
2. Считываем массив из n чисел.
3. Строим массив префиксных сумм pref длины n + 1:
   • pref[0] = 0
   • для i от 1 до n:
     • pref[i] = pref[i - 1] + a[i - 1] в Python
     • или читаем число сразу и записываем pref[i] = pref[i - 1] + x в C++
4. Для каждого запроса (l, r) выводим:
   • pref[r] - pref[l - 1]

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

Докажем корректность.

Пусть:

• pref[r] = a[1] + a[2] + ... + a[r]
• pref[l - 1] = a[1] + a[2] + ... + a[l - 1]

Тогда разность:

pref[r] - pref[l - 1]

равна:

(a[1] + ... + a[l - 1] + a[l] + ... + a[r]) - (a[1] + ... + a[l - 1])

Все слагаемые от a[1] до a[l - 1] сокращаются, остаётся:

a[l] + a[l + 1] + ... + a[r]

Это именно сумма на отрезке [l, r].

Значит, для каждого запроса формула даёт правильный ответ.

5. Сложность

Построение массива префиксных сумм:

• O(n)

Обработка одного запроса:

• O(1)

Обработка всех запросов:

• O(q)

Итоговая сложность:

• O(n + q)

Память:

• O(n)

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

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

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

    return 0;
}

7. Код на Python 3

n, q = map(int, input().split())
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]

for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])