1. Идея

Нужно много раз находить сумму на отрезке массива: для каждого запроса с границами l и r требуется вычислить сумму элементов с l по r.

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

Поэтому нужно заранее сделать подготовку массива так, чтобы потом отвечать на каждый запрос очень быстро. Для этого используются префиксные суммы.

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

Пусть pref[i] — сумма первых i элементов массива.

Тогда:

• pref[0] = 0
• 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

Например, для массива 1, -2, 3, 0, 4:

• pref = [0, 1, -1, 2, 2, 6]

Тогда сумма на отрезке [2, 5]:

• pref[5] - pref[1] = 6 - 1 = 5

Это и есть ответ.

3. Алгоритм

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

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

Докажем корректность формулы pref[r] - pref[l - 1].

По определению:

• pref[r] = a[1] + a[2] + ... + a[l - 1] + a[l] + ... + a[r]
• pref[l - 1] = a[1] + a[2] + ... + 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) на массив префиксных сумм

Важно: ответы могут не помещаться в 32-битный тип, поэтому в C++ нужен тип long long.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    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;
    }

    int q;
    cin >> q;

    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 = 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())
for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])