1. Идея

Нужно найти сумму элементов массива на отрезке от l до r включительно.

Если просто складывать числа с l по r, это тоже даст ответ, но в этой задаче удобно использовать префиксные суммы — стандартный приём для быстрых вычислений сумм на отрезках.

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

pre[r] - pre[l - 1]

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

Пусть дан массив расходов:

a[1], a[2], ..., a[n]

Определим префиксные суммы так:

• pre[0] = 0
• pre[1] = a[1]
• pre[2] = a[1] + a[2]
• ...
• pre[i] = a[1] + a[2] + ... + a[i]

Тогда:

• pre[r] — сумма от первого дня до r
• pre[l - 1] — сумма от первого дня до дня перед l

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

Пример:

массив [-1, 2, -3, 4, -5]

Префиксные суммы:

• pre[0] = 0
• pre[1] = -1
• pre[2] = 1
• pre[3] = -2
• pre[4] = 2
• pre[5] = -3

Для отрезка 2..4 получаем:

pre[4] - pre[1] = 2 - (-1) = 3

Это и есть сумма 2 + (-3) + 4 = 3.

Также важно, что ответ может не поместиться в 32-битный тип, поэтому в C++ нужен long long.

3. Алгоритм

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

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

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

pre[r] = a[1] + a[2] + ... + a[r]

и

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

Вычтем второе из первого. Все элементы от a[1] до a[l - 1] сократятся, и останется:

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

Это и есть сумма расходов на нужном промежутке дней.

Значит, формула pre[r] - pre[l - 1] всегда даёт правильный ответ.

5. Сложность

• Построение префиксного массива: O(n)
• Получение ответа: O(1)
• Общая сложность: O(n)
• Дополнительная память: 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 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()))
l, r = map(int, input().split())

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

print(pre[r] - pre[l - 1])