1. Идея

В каждом запросе нужно найти сумму элементов массива на отрезке [l, r], но учитывать только те элементы, которые стоят на чётных позициях массива: 2, 4, 6, ....

Если для каждого запроса перебирать все позиции от l до r, получится слишком медленно: при больших n и q это может дать до O(nq) операций.

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

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

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

Тогда:

• если позиция i нечётная, то pref[i] = pref[i - 1];
• если позиция i чётная, то pref[i] = pref[i - 1] + a[i].

Тогда сумма по чётным позициям на отрезке [l, r] равна:

pref[r] - pref[l - 1]

Почему это верно:

• pref[r] содержит сумму всех элементов на чётных позициях от 1 до r;
• pref[l - 1] содержит сумму всех элементов на чётных позициях от 1 до l - 1;
• если вычесть вторую сумму из первой, останутся только чётные позиции внутри [l, r].

3. Алгоритм

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

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

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

После построения массива pref[i] действительно хранит сумму всех a[j], где:

• 1 <= j <= i
• j чётно

Это верно по построению:

• база: pref[0] = 0, сумма на пустом префиксе равна нулю;
• переход:
  • если i нечётно, новый элемент не должен учитываться, значит сумма не меняется;
  • если i чётно, новый элемент должен учитываться, значит прибавляем a[i].

Теперь рассмотрим запрос [l, r].

pref[r] содержит сумму по всем чётным позициям до r, а pref[l - 1] — сумму по всем чётным позициям до позиции перед l. Значит их разность оставляет ровно чётные позиции из отрезка [l, r].

Следовательно, ответ вычисляется правильно.

5. Сложность

Построение префиксного массива:

• O(n)

Ответ на каждый запрос:

• O(1)

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

• O(n + q)

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

• O(n)

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];
        if (i % 2 == 0) {
            pref[i] += 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]
    if i % 2 == 0:
        pref[i] += a[i - 1]

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