Сумма на круговом отрезке

1. Идея

Нужно много раз находить сумму на отрезке в массиве, который считается циклическим.

Если бы массив был обычным, задача решалась бы префиксными суммами:

• заранее посчитать массив pre, где pre[i] — сумма первых i элементов;
• тогда сумма на отрезке от l до r равна pre[r] - pre[l - 1].

В этой задаче массив круговой, поэтому есть два случая:

• l <= r: обычный отрезок;
• l > r: отрезок проходит через конец массива, значит состоит из двух частей:
  • от l до n,
  • от 1 до r.

Обе части тоже удобно считать через префиксные суммы.

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

Наблюдение 1

Для обычного отрезка l..r сумма равна:

pre[r] - pre[l - 1]

Наблюдение 2

Если l > r, то круговой участок можно разбить так:

• хвост массива: l..n
• начало массива: 1..r

Тогда ответ:

sum(l..n) + sum(1..r)

Через префиксные суммы это:

• sum(l..n) = pre[n] - pre[l - 1]
• sum(1..r) = pre[r]

Итог:

(pre[n] - pre[l - 1]) + pre[r]

Наблюдение 3

Значения элементов могут быть отрицательными, а ответы — большими по модулю, поэтому нужен 64-битный целый тип:

• в C++ это long long;
• в Python специальные меры не нужны, там целые числа длинные автоматически.

3. Алгоритм

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

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

Докажем корректность по случаям.

Случай 1: l <= r

Тогда нужный участок не проходит через конец массива и является обычным отрезком l..r.

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

• pre[r] — сумма элементов от 1 до r,
• pre[l - 1] — сумма элементов от 1 до l - 1.

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

Значит ответ равен pre[r] - pre[l - 1].

Случай 2: l > r

Тогда участок круговой и проходит через конец массива. Он состоит из двух непересекающихся частей:

• от l до n,
• от 1 до r.

Сумма на первой части равна pre[n] - pre[l - 1], потому что это сумма от 1 до n без первых l - 1 элементов.

Сумма на второй части равна pre[r].

Так как участок состоит ровно из этих двух частей, общий ответ равен:

(pre[n] - pre[l - 1]) + pre[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> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;

        long long ans;
        if (l <= r) {
            ans = pre[r] - pre[l - 1];
        } else {
            ans = (pre[n] - pre[l - 1]) + pre[r];
        }

        cout << ans << '\n';
    }

    return 0;
}

7. Код на Python 3

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

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

q = int(input())

for _ in range(q):
    l, r = map(int, input().split())
    if l <= r:
        print(pre[r] - pre[l - 1])
    else:
        print((pre[n] - pre[l - 1]) + pre[r])