n.
l
r
В информатике префиксной суммой последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, такая что: y0 = x0 y1 = x0 + x1 y2 = x0 + x1+ x2 ... Идея решения заключается в том, чтобы сохранить в дополнительный массив сумму всех элементов префиксов последовательности. В элемент с индексом 1 - значение суммы элементов префикса длиной 1 (значение первого элемента массива). В элемент с индексом 2 - значение суммы элементов префикса длиной 2 (сумма первого и второго элементов массива) и т.д.
prefix
Используя сформированный массив (prefix), можно легко вычислять сумму на отрезке [l; r]: prefix[r] - prefix[l-1], где prefix[r] - сумма первых r элементов последовательности, prefix[l-1] - сумма первых l-1 элементов последовательности.
[l; r]
[r] -
[l-1]
[r]
l-1
n
q
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач