1. Идея

Для каждого запроса дано число k, и нужно найти сумму первых k элементов массива.

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

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

• pref[0] = 0
• pref[1] = a_1
• pref[2] = a_1 + a_2
• ...
• pref[i] = a_1 + a_2 + ... + a_i

Тогда ответ на запрос с числом k будет просто pref[k].

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

1. Все запросы имеют одинаковый вид: нужна сумма префикса.
2. Префиксные суммы идеально подходят для таких задач.
3. Массив pref удобно хранить длины n + 1, чтобы:
   • pref[0] = 0
   • pref[i] = pref[i - 1] + a[i - 1]
4. Ответ на каждый запрос получается за O(1).
5. Так как элементы массива могут быть до 10^9, а n до 2 * 10^5, сумма может быть большой.
   Поэтому в C++ нужно использовать тип long long.

3. Алгоритм

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

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

По определению префиксной суммы:

• pref[0] = 0
• pref[1] = a_1
• pref[2] = a_1 + a_2
• ...
• pref[k] = a_1 + a_2 + ... + a_k

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

Почему формула построения верна:

• сумма первых i элементов равна сумме первых i - 1 элементов плюс i-й элемент;
• значит, pref[i] = pref[i - 1] + a[i - 1], если массив a хранится с индексацией с нуля.

После предвычисления массива pref ответ на любой запрос находится сразу, без повторного суммирования элементов.

5. Сложность

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

По памяти:

• массив a: O(n)
• массив pref: O(n)

Итого: O(n) дополнительной памяти.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

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

    for (int i = 0; i < q; i++) {
        int k;
        cin >> k;
        if (i > 0) {
            cout << ' ';
        }
        cout << pref[k];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

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

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

answers = []
for k in queries:
    answers.append(str(pref[k]))

print(" ".join(answers))