1. Идея

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

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

Поэтому нужно заранее подготовить массив префиксных сумм.

Пусть pre[i] — сумма первых i элементов массива. Тогда сумма на отрезке [l, r] равна:

pre[r] - pre[l - 1]

Это позволяет отвечать на каждый запрос за O(1).

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

Наблюдение 1

Если знать сумму первых r дней и сумму первых l - 1 дней, то разность этих сумм даст сумму только на нужном отрезке [l, r].

Например, если массив такой:

a = [5, 2, 7, 1]

Тогда:

• pre[1] = 5
• pre[2] = 7
• pre[3] = 14
• pre[4] = 15

Сумма на отрезке [2, 4]:

a[2] + a[3] + a[4] = 2 + 7 + 1 = 10

Через префиксные суммы:

pre[4] - pre[1] = 15 - 5 = 10

Наблюдение 2

Удобно завести массив pre длины n + 1, где:

• pre[0] = 0
• pre[i] = pre[i - 1] + a[i], если считать элементы с единицы

Тогда формула для любого запроса выглядит одинаково:

pre[r] - pre[l - 1]

и не нужно отдельно обрабатывать случай l = 1.

Наблюдение 3

Так как элементы массива могут быть до 10^9 по модулю, а элементов много, ответ может не помещаться в 32-битный тип.

Поэтому:

• в C++ нужен тип long long
• в Python это не проблема, так как int поддерживает большие числа

3. Алгоритм

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

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

Докажем, что ответ на запрос [l, r] равен pre[r] - pre[l - 1].

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

• pre[r] — сумма элементов от 1 до r
• pre[l - 1] — сумма элементов от 1 до l - 1

Если из суммы элементов от 1 до r вычесть сумму элементов от 1 до l - 1, то элементы до l - 1 сократятся, и останется только сумма от l до r.

То есть:

pre[r] - pre[l - 1] = a[l] + a[l + 1] + ... + a[r]

Именно это и требуется в задаче.

Так как префиксные суммы посчитаны правильно для всех позиций, каждый запрос тоже обрабатывается правильно.

5. Сложность

• Построение массива префиксных сумм: O(n)
• Ответы на q запросов: O(q)
• Общая сложность: O(n + q)

Дополнительная память:

• массив pre размера n + 1, то есть O(n)

6. Код на 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;
}

7. Код на Python 3

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

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

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