Разбор

Каждый запрос $S_{l, r}$ можно выполнять при помощи цикла за время $O (n)$ . Имеется $m \leq 1 0^{6}$ запросов, длина массива составляет $n \leq 1 0^{6}$ . При линейном времени выполнения запроса нам потребуется не более $n \times m \leq 1 0^{12}$ операций, что даст Time Limit.

Рассмотрим частичные суммы массива $a$ :

s_{1} = a_{1}; s_{2} = a_{1} + a_{2}; s_{3} = a_{1} + a_{2} + a_{3}; ... s_{n} = a_{1} + a_{2} + a_{3} + ... + a_{n};

Вычислить значения $s_{1}, s_{2}, ..., s_{n}$ можно в линейном массиве $s$ за время $O (n)$ .

Далее заметим, что

S_{l, r} = a_{l} + a_{l + 1} + ... + a_{r} = (a_{1} + ... + a_{l} + a_{l + 1} + ... + a_{r}) - (a_{1} + ... + a_{l - 1}) = s_{r} - s_{l - 1}

Таким образом ответить на запрос $S_{l, r}$ можно за $O (1)$ , то есть за константное время.

Пример

Вычислим сумму $a_{3} + a_{4} + a_{5}$ для приведенного в условии примера.

Имеем: $a_{3} + a_{4} + a_{5} = s_{5} - s_{2} = 15 - 3 = 12.$

Реализация алгоритма

Объявим два рабочих двумерных массива.

#define MAX 1000001
int a[MAX], s[MAX];

Читаем входной набор чисел в массив $a$ , вычисляем частичные суммы в массиве $s$ .

scanf("%d",&n); 
s[0] = 0;
for(i = 1; i <= n; i++)
{
  scanf("%d",&a[i]);
  s[i] = s[i-1] + a[i];
}

Обрабатываем $m$ запросов.

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&b,&c);
  printf("%d\n",s[c] - s[b-1]);
}

Python реализация

Читаем входные данные.

n = int(input())
a = [0] + list(map(int, input().split()))

В списке $s$ вычисляем частичные суммы списка $a$ .

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

Обрабатываем $m$ запросов.

m = int(input())
for _ in range(m):
  b, c = map(int, input().split())
  print(s[c] - s[b - 1])