1. Идея

Для каждого запроса нужно быстро находить:

• сумму элементов на нечётных позициях внутри отрезка [l, r];
• сумму элементов на чётных позициях внутри отрезка [l, r].

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

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

Подход стандартный: построим две префиксные суммы:

• pref_odd[i] — сумма всех элементов на нечётных позициях среди первых i элементов;
• pref_even[i] — сумма всех элементов на чётных позициях среди первых i элементов.

Тогда ответ на запрос [l, r] можно получить вычитанием:

• S_odd = pref_odd[r] - pref_odd[l - 1]
• S_even = pref_even[r] - pref_even[l - 1]

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

Наблюдение 1

Позиции считаются от 1, а не от 0.

Это важно:

• позиция 1 — нечётная,
• позиция 2 — чётная,
• позиция 3 — нечётная,
• и так далее.

Наблюдение 2

Если хранить одну обычную префиксную сумму, то она даст сумму всех элементов на отрезке, но не разделит их по чётности позиции.

Поэтому нужны именно две отдельные суммы.

Наблюдение 3

При построении префиксов для позиции i:

• сначала копируем значения с предыдущей позиции:
  • pref_odd[i] = pref_odd[i - 1]
  • pref_even[i] = pref_even[i - 1]
• затем добавляем текущий элемент либо в нечётную сумму, либо в чётную.

Например, если i нечётно, то:

• pref_odd[i] += a[i],
• pref_even[i] не меняется.

Наблюдение 4

Префиксная сумма на отрезке [l, r] всегда считается как:

префикс до r минус префикс до l - 1.

Это работает и для нечётных, и для чётных позиций отдельно.

3. Алгоритм

1. Считываем n и q.
2. Считываем массив.

3. Создаём два массива длины n + 1:

   • pref_odd
   • pref_even

   Нулевой элемент у обоих равен 0.

4. Для каждой позиции i от 1 до n:
   • переносим предыдущие значения:
     • pref_odd[i] = pref_odd[i - 1]
     • pref_even[i] = pref_even[i - 1]
   • если i нечётно, добавляем текущий элемент в pref_odd[i];
   • иначе добавляем его в pref_even[i].
5. Для каждого запроса (l, r):
   • считаем
     • sum_odd = pref_odd[r] - pref_odd[l - 1]
     • sum_even = pref_even[r] - pref_even[l - 1]
   • выводим эти два числа.

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

Докажем, что алгоритм действительно выдаёт правильный ответ.

Построение префиксов

Рассмотрим pref_odd[i].

По определению, в нём должна храниться сумма элементов на нечётных позициях среди первых i элементов.

При переходе от i - 1 к i возможны два случая:

• если i нечётно, то нужно добавить a[i] в сумму нечётных позиций;
• если i чётно, то сумма нечётных позиций не меняется.

Именно это и делает алгоритм.

Аналогично строится pref_even[i].

Значит:

• pref_odd[i] корректно хранит сумму элементов на нечётных позициях от 1 до i;
• pref_even[i] корректно хранит сумму элементов на чётных позициях от 1 до i.

Ответ на запрос

Нужно найти сумму на отрезке [l, r].

Сумма нечётных позиций на отрезке [l, r] равна:

• сумме нечётных позиций на префиксе [1, r]
• минус сумме нечётных позиций на префиксе [1, l - 1].

То есть:

pref_odd[r] - pref_odd[l - 1].

Полностью так же для чётных позиций:

pref_even[r] - pref_even[l - 1].

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

5. Сложность

По времени

• построение двух префиксных массивов: O(n)
• обработка q запросов: O(q)

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

O(n + q)

По памяти

Храним:

• массив из n чисел в Python-версии,
• два префиксных массива длины n + 1.

Итого:

O(n)

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> pref_odd(n + 1, 0), pref_even(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref_odd[i] = pref_odd[i - 1];
        pref_even[i] = pref_even[i - 1];
        if (i % 2 == 1) {
            pref_odd[i] += x;
        } else {
            pref_even[i] += x;
        }
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        long long sum_odd = pref_odd[r] - pref_odd[l - 1];
        long long sum_even = pref_even[r] - pref_even[l - 1];
        cout << sum_odd << " " << sum_even << "\n";
    }

    return 0;
}

7. Код на Python 3

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

pref_odd = [0] * (n + 1)
pref_even = [0] * (n + 1)

for i in range(1, n + 1):
    x = a[i - 1]
    pref_odd[i] = pref_odd[i - 1]
    pref_even[i] = pref_even[i - 1]
    if i % 2 == 1:
        pref_odd[i] += x
    else:
        pref_even[i] += x

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