Префиксная сумма
Префиксные суммы очень удобны при работе с диапазонами в массивах. Во многих случаях можно существенно ускорить программы, используя префиксную сумму массива вместо того, чтобы каждый раз вычислять сумму элементов заново.
Представьте задачу, в которой нужно многократно (миллионы раз) отвечать на запрос: «Какова сумма элементов массива
a от начала до ?». Простое решение могло бы заключаться в вычислении суммы a[0] + a[1] + a[2] + ... + a[] для каждого запроса. Например, рассмотрим массив и запросы:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesМы могли бы запускать цикл
for для суммирования a[0] + a[1] + a[2] + ... + a[] при каждом запросе, что приводит к множественному повторению вычислений:res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Заметьте, что первая часть вычислений почти всегда повторяется. Перед тем как посчитать
res2, мы уже знаем результат a[0] + a[1] + a[2] + a[3], который остался от res1. Перед вычислением res4 мы уже знаем сумму a[0] + a[1] + a[2] + a[3] + a[4] + a[5]. Очевидно, эти вычисления можно оптимизировать и отвечать на запросы мгновенно, не запуская каждый раз цикл.Чтобы это сделать, мы можем сохранить в новом массиве
p так называемые префиксные суммы, где каждый элемент p будет представлять собой сумму элементов исходного массива a от начала до соответствующего индекса. Тогда для ответа на запрос достаточно просто взять один элемент из массива префиксных сумм:p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Здесь можно заметить закономерность: чтобы вычислить следующий элемент в массиве
p, мы берем предыдущий результат и добавляем к нему один новый элемент из a. Это позволяет опираться на уже готовые результаты вместо повторного сложения одних и тех же чисел:p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]Такой подход можно реализовать за один проход
for, что работает за линейное время, вместо многократных циклов с повторяющимися вычислениями. После построения массива префиксных сумм p, мы сможем мгновенно отвечать на запросы, ведь в p[i] уже хранится сумма a[0] + a[1] + a[2] + ... + a[i]. Следовательно, для запроса ответом будет просто p[].Сможете ли вы теперь вычислить массив префиксных сумм?
Входные данные
В первой строке входного файла содержится одно целое число
n (1 ≤ n ≤ ). Во второй строке записаны n целых чисел, разделенных пробелами, которые представляют массив a .Вывод
Программа должна вывести массив префиксных сумм для
a.Примеры
Input | Output |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 20 MB