Суммы префиксов — это промежуточные итоги чисел массива. Это еще одна полная последовательность чисел. Например, рассмотрим следующий список:
5, 2, —6, 8, —4, 0, 9, 3, —1, 7
Есть десять элементов. Представьте 0, который предшествует этому списку.
Тогда 0 + 5 = 5 — первая сумма префикса.
0 + 5 + 2 = 7 — сумма следующего префикса.
0 + 5 + 2 + — 6 = 1 — сумма префикса после.
0 + 5 + 2 + — 6 + 8 = 9 — новая сумма префиксов.
Этот промежуточный итог обычно продолжается до последнего элемента, 7, в данном списке. Вторая последовательность (список) имеет префиксные суммы одиннадцати элементов. Первый элемент в массиве сумм префиксов (вторая последовательность) является предполагаемым (воображаемым) нулем. Следующие две таблицы, где вторая строка для каждой таблицы имеет индексы массива с отсчетом от нуля, иллюстрируют эти две последовательности:
| Данная таблица | ||||||||||
| 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| Таблица сумм префиксов | ||||||||||
| 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Первая таблица предназначена для данного массива, а вторая — для массива префиксных сумм. Если количество элементов в данном массиве равно n, то количество элементов в массиве префиксных сумм равно n+1. В этой статье объясняются основные особенности сумм префиксов. В данном контексте «пре-» означает то, что было добавлено ранее. Это также может означать добавление нуля к массиву префиксов.
Brute Force
Программист должен знать значение грубой силы, используемой в программировании. Грубая сила означает решение проблемы с использованием прямого алгоритма, который обычно не так эффективен (использует меньше времени и памяти), как другой тщательно обученный алгоритм.
Сумма префикса методом грубой силы
Чтобы создать массив сумм префиксов методом грубой силы для указанного выше массива, 5 сначала будет отмечено как первая сумма префикса. Затем будут добавлены 5 и 2, чтобы получить следующую сумму префикса, 7. Затем будут добавлены 5, 2 и −6, чтобы получить сумму префикса после 1. Затем 5, 2, −6 и 8 будут добавлены к дать новую сумму префикса, 9, и так далее. Эта процедура может быть утомительной.
Утомительный или нет, код для создания массива суммы префиксов из предполагаемого нуля методом грубой силы:
int n = 10;
int A[] = {5, 2, —6, 8, —4, 0, 9, 3, —1, 7};
int P[n+1];
P[0] = 0;for (int i=0; i<n; i++) {
int sum = 0;
int j;
for (j=0; j<i+1; j++) {
sum = sum + A[j];
}
P[j] = sum;
}
Внешний цикл for повторяется от 0 до чуть меньше n. Внутренний цикл for повторяется от 0 до i, индекс итерации внешнего цикла. При этом имеется 55 основных операций. Временная сложность для этого O (n.log 2 n).
Префиксные суммы в линейном времени
Предыдущая временная сложность приблизительно равна O(n.log 2 n). Алгоритм можно улучшить таким образом, чтобы суммы производились за линейное время для временной сложности O (n). Префикс в этом контексте означает добавление суммы всех предыдущих элементов к текущему заданному элементу. Рассмотрим две предыдущие таблицы, нарисованные как одна таблица, с некоторыми изменениями:
| Таблица сумм префиксов | ||||||||||
| Данный: | 5 | 2 | -6 | 8 | -4 | 0 | 9 | 3 | -1 | 7 |
| 0 + 5 = | 5 + 2 = | 7 + -6 = | 1 + 8 = | 9 + -4 = | 5 + 0 = | 5 + 9 = | 14+3 = | 17+ -1= | 16+7 = | |
| 0 | 5 | 7 | 1 | 9 | 5 | 5 | 14 | 17 | 16 | 23 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Первая строка в этой таблице содержит заданные элементы в назначенных им позициях. Для второй и третьей строк предполагается начальный нуль. Для второй и третьей строк каждый элемент равен сумме всех предыдущих элементов плюс текущий элемент. Последняя строка имеет индексы массива сумм префикса (начиная с нуля). Обратите внимание, что массив префиксных сумм на один элемент длиннее заданного массива.
Этот алгоритм создает массив сумм префиксов за линейное время временной сложности O(n). То есть примерно n операций. И рекомендуемый код суммы префиксов в С++ для временной сложности O (n):
int n = 10;
int A[] = {5, 2, —6, 8, —4, 0, 9, 3, —1, 7};
int P[n+1];
P[0] = 0;for (int i=1; i<n+1; i++) {
P[i] = P[i—1] + A[i—1];
}
Обратите внимание, что на этот раз нет вложенного цикла. Операторы в скобках цикла for необходимы. Основная операция тела цикла for также важна. Как и прежде, цикл for выполняет итерации от 1 до менее чем n+1, а не от 0 до менее чем n. Утверждение тела цикла for:
P[i] = P[i-1] + A[i-1];
Это означает, что текущее значение данного массива добавляется к предыдущей сумме префикса, чтобы получить текущую сумму префикса.
Общая проблема для сумм префиксов
Обратите внимание, что к соответствующему индексу массива префиксных сумм добавлено 1 по сравнению с индексом данного массива.
Распространенной проблемой для сумм префиксов является эффективное нахождение суммы подмассива последовательных элементов. Это сумма среза. Слово «эффективно» означает, что алгоритм грубой силы не должен использоваться. Предельными индексами для подмассива являются x и y. Рассмотрим приведенный список:
5, 2, —6, 8, —4, 0, 9, 3, —1, 7
Сумма подмассива от элемента 8 до элемента 9:
8 + —4 + 0 + 9 = 13
8 находится в индексе 3, для x; и 9 находится в индексе 6 для y. Эффективный способ сделать это — вычесть сумму префикса в индексе 2 для данного массива из суммы префикса в индексе 6 для данного массива. Для массива префиксов это индекс y+1 и индекс x. Добавляемый 1 удаляется, чтобы получить индекс массива префиксов, показанный ниже, и эффективный код:
int n = 10;
int A[] = {5, 2, —6, 8, —4, 0, 9, 3, —1, 7};
int P[n+1];
P[0] = 0;
int x=3, y=6;for (int i=1; i<n+1; i++) {
P[i] = P[i—1] + A[i—1];
}int sliceSum = P[y+1] — P[x];
cout<<sliceSum<<endl;
Вывод 13, как и ожидалось, но из эффективного кода.
Заключение
Суммы префиксов — это промежуточные итоги элементов массива. Задействованы два массива: заданный массив и созданный массив сумм префиксов. Массив префиксных сумм длиннее заданного массива на один элемент. Основная операция для получения элементов массива префиксов: текущее значение в массиве сумм префиксов равно предыдущей сумме префиксов плюс текущее значение данного массива. Чтобы получить сумму среза из заданного массива, используйте: int sliceSum = P[y+1] — P[x];
Где x — индекс нижнего предела среза в данном массиве, а y — индекс верхнего предела среза в данном массиве.
