1. Идея

В каждом запросе нужно найти сумму на отрезке [l, r], где знаки чередуются и первый элемент берётся со знаком +:

a_l - a_{l+1} + a_{l+2} - ...

Если считать такую сумму для каждого запроса напрямую, то один запрос может занимать O(r - l + 1), а при больших n и q это слишком медленно.

Главная идея — заранее построить специальную префиксную сумму по всему массиву, в которой:

• элементы на нечётных позициях прибавляются,
• элементы на чётных позициях вычитаются.

Тогда любой запрос можно будет отвечать за O(1).

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

Рассмотрим массив:

a_1, a_2, a_3, a_4, ...

Построим новый знакопеременный ряд от начала массива:

a_1 - a_2 + a_3 - a_4 + ...

То есть для позиции i:

• если i нечётное, берём +a_i,
• если i чётное, берём -a_i.

Теперь пусть нужно ответить на запрос [l, r].

Если просто взять сумму этого преобразованного массива на отрезке [l, r], получится:

• a_l - a_{l+1} + a_{l+2} - ..., если l нечётное;
• -a_l + a_{l+1} - a_{l+2} + ..., если l чётное.

То есть:

• для нечётного l ответ уже совпадает с требуемым;
• для чётного l ответ имеет противоположный знак, значит его нужно умножить на -1.

Итак:

1. считаем сумму знакопеременного массива на [l, r];
2. если l чётное, меняем знак.

3. Алгоритм

Построение

Создадим массив префиксных сумм pref, где:

• pref[0] = 0
• pref[i] = pref[i - 1] + x
• x = a_i, если i нечётное
• x = -a_i, если i чётное

То есть pref[i] хранит сумму:

a_1 - a_2 + a_3 - a_4 + ... ± a_i

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

Для запроса [l, r] сначала находим сумму на отрезке в этом преобразованном массиве:

pref[r] - pref[l - 1]

Дальше:

• если l нечётное, это и есть ответ;
• если l чётное, нужно поменять знак.

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

Пусть b_i — преобразованный массив:

• b_i = a_i, если i нечётное,
• b_i = -a_i, если i чётное.

Тогда сумма b_l + b_{l+1} + ... + b_r находится через префиксные суммы как:

pref[r] - pref[l - 1]

Разберём два случая.

Случай 1: l нечётное

Тогда:

• b_l = a_l
• b_{l+1} = -a_{l+1}
• b_{l+2} = a_{l+2}

Получаем ровно:

a_l - a_{l+1} + a_{l+2} - ...

Это и есть нужная сумма.

Случай 2: l чётное

Тогда:

• b_l = -a_l
• b_{l+1} = a_{l+1}
• b_{l+2} = -a_{l+2}

Получаем:

-a_l + a_{l+1} - a_{l+2} + ...

Это противоположно требуемой сумме:

a_l - a_{l+1} + a_{l+2} - ...

Значит, достаточно умножить результат на -1.

Поэтому формула ответа полностью корректна:

1. s = pref[r] - pref[l - 1]
2. если l чётное, то s = -s

5. Сложность

По времени

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

Итоговая сложность: O(n + q)

По памяти

Хранится массив префиксных сумм длины 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(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        if (i % 2 == 0) {
            x = -x;
        }
        pref[i] = pref[i - 1] + x;
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        long long s = pref[r] - pref[l - 1];
        if (l % 2 == 0) {
            s = -s;
        }
        cout << s << '\n';
    }

    return 0;
}

7. Код на Python 3

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

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

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