Подразделы

Другие разделы

Дата и время

04/04/2025 10:12:27

Авторизация

Пространственно-временной компромисс

Идея пространственно-временного компромисса Массив частичных сумм Сортировка подсчетом Хеширование Вычисление биномиальных коэффициентов Задача о рюкзаке

Массив частичных сумм

Элемент $S[i]$ массива частичных сумм содержит сумму элементов массива $A$ с 0 до $i$ .

Алгоритм PartialSum( $A$ )
// Входные данные: Массив $A[0...n-1]$
// Выходные данные: Массив частичных сумм $S[0...n-1]$
$S[0] larr A[0]$
for $i in [1..n-1]$ do
$quad S[i] larr S[i-1]+A[i]$

Кроме префикс-сумм, в некоторых задачах могут использоваться суффикс-суммы.

Такой вспомогательный массив нужен для быстрого нахождения суммы элементов массива с $i$ до $j$ :

Алгоритм Sum( $S,i,j$ )
if $i>0$
$quad$ return $S[j]-S[i-1]$
else
$quad$ return $S[j]$