Быстрые запросы по диапазонам
Вам дан массив
a из n целых чисел, и требуется ответить на q запросов. Каждый запрос задаётся вопросом: «Какова сумма элементов массива a в пределах индексов [l; r]?» (оба конца включаются, при этом индексация начинается с 0). В этот раз количество запросов и размер массива гораздо больше. Может ли найтись способ отвечать на такие запросы быстрее?Входные данные
Первая строка входа содержит одно целое число
n — количество элементов в массиве (1 ≤ n ≤ ). Следующая строка содержит n целых чисел, записанных через пробел, которые составляют массив .Далее следует строка с одним целым числом
q — количеством запросов (1 ≤ q ≤ ). В следующих q строках идут запросы формата .Выходные данные
Программа должна вывести
q строк, где каждая строка представляет собой сумму элементов массива a между индексами (оба конца включаются).Примеры
Входные данные | Вывод |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 25 MB