Задача
Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$
Входные данные
В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.
Выходные данные
Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 5 1 2 3 4 5 5 1 5 2 3 3 4 2 5 1 4 |
15 5 7 14 10 |
| 2 | 10 10 10 10 10 10 10 10 10 10 10 5 1 3 3 5 5 7 7 9 3 7 |
30 30 30 30 50 |
| 3 | 10 57 42 24 73 98 71 65 76 12 33 7 1 2 4 5 8 10 1 10 7 10 2 5 3 8 |
99 171 121 551 186 237 407 |
| 4 | 3 10 15 20 2 1 2 1 3 |
25 45 |
| 5 | 7 299 38924 2388 4399 7549 79475 57947 10 1 3 2 3 3 3 4 7 6 7 3 5 5 5 6 6 1 6 1 7 |
41611 41312 2388 149370 137422 14336 7549 79475 133034 190981 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; int main() { std::ios::sync_with_stdio(false); int n; cin>>n; long long a[n]; for (int i = 0; i < n; i++) { cin>>a[i]; } long long summ[n + 1]; summ[0] = 0; for (int i = 1; i < n + 1; i++) { summ[i] = summ[i - 1] + a[i - 1]; } int m; cin>>m; while (m--) { int l, r; cin>>l>>r; printf("%d", summ[r] - summ[l - 1]); printf("%s", "\n"); } } |
Решение
Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.
Условие задачи можно найти на e-olymp
Код решения — ideone