В области компьютерного программирования и решения алгоритмических задач концепция массива сумм префиксов оказалась мощным инструментом. Являетесь ли вы опытным программистом или только начинаете, понимание и использование массивов сумм префиксов может значительно повысить вашу способность эффективно решать различные типы задач. В этом подробном руководстве мы углубимся в построение и применение массивов сумм префиксов. Итак, давайте углубимся и раскроем потенциал массивов сумм префиксов.
Индекс
- Что такое массив сумм префиксов?
- Построение массива суммы префиксов
- Понимание массива суммы префиксов на примере
- Заключение
Что такое массив сумм префиксов?
Массив сумм префиксов, также известный как массив кумулятивных сумм, представляет собой производный массив, в котором хранится кумулятивная сумма элементов в данном массиве. Каждый элемент в массиве сумм префиксов представляет собой сумму всех элементов до этого индекса в исходном массиве. Он действует как предшественник ответов на запросы, связанные с кумулятивными суммами, что позволяет выполнять быстрые и эффективные вычисления. Это также снижает временную сложность, давая нам выход из TLE.
Построение массива суммы префиксов
Чтобы создать одномерный массив суммы префиксов, мы перебираем входной массив и вычисляем кумулятивную сумму для каждого индекса. Значение суммы префикса в индексе i является суммой всех элементов от индекса 0 до i в исходном массиве. Вот шаги, связанные с построением массива суммы префиксов:
- Инициализируйте массив, скажем, prefixSum[], такой же длины, как и входной массив.
- Установите первый элемент prefixSum[] таким же, как первый элемент входного массива.
- Перебрать входной массив, начиная со второго элемента.
- Для каждого элемента вычислите сумму префикса, добавив текущий элемент со значением суммы префикса предыдущего индекса.
- Присвойте значение суммы префикса соответствующему индексу в массиве prefixSum.
- Повторяйте шаги 3–5, пока не будет достигнут конец входного массива.
Пример времени
Возьмем пример, чтобы понять. Предположим, у нас есть входной массив A = [3, 1, 5, 2, 4]. Мы рассмотрим этапы построения массива сумм префиксов на этом примере.
Шаг 1. Создайте массив, скажем, pf[], который имеет тот же размер, что и входной массив, который в данном случае равен 5.
Шаг 2. Инициализируйте массив суммы префиксов и назначьте ему первый элемент входного массива.
Массив суммы префиксов: [3, _, _, _, _]
Шаг 3. Перебор входного массива, начиная со второго элемента.
Текущий элемент: 1
Шаг 4. Вычислите сумму префикса, добавив текущий элемент со значением суммы префикса предыдущего индекса.
Сумма префикса в индексе 1 = Сумма префикса в индексе 0 + Текущий элемент
Сумма префикса по индексу 1 = 3 + 1 = 4
Шаг 5. Назначьте вычисленное значение суммы префиксов соответствующему индексу в массиве сумм префиксов.
Массив суммы префиксов: [3, 4, _, _, _]
Шаг 6. Повторите шаги 4–5 для остальных элементов входного массива.
Текущий элемент: 5
Сумма префиксов в индексе 2 = Сумма префиксов в индексе 1 + Текущий элемент
Сумма префикса по индексу 2 = 4 + 5 = 9
Массив суммы префиксов: [3, 4, 9, _, _]
Текущий элемент: 2
Сумма префикса в индексе 3 = Сумма префикса в индексе 2 + Текущий элемент
Сумма префикса в индексе 3 = 9 + 2 = 11
Массив суммы префиксов: [3, 4, 9, 11, _]
Текущий элемент: 4
Сумма префикса в индексе 4 = Сумма префикса в индексе 3 + Текущий элемент
Сумма префикса по индексу 4 = 11 + 4 = 15
Массив сумм префиксов: [3, 4, 9, 11, 15]
Шаг 7: построение завершено, и у нас есть массив сумм префиксов для заданного входного массива.
Массив сумм префиксов: [3, 4, 9, 11, 15]
def construct_prefix_sum_array(arr):
n = len(arr)
prefix_sum = [0] * n
prefix_sum[0] = arr[0]
for i in range(1, n):
prefix_sum[i] = prefix_sum[i — 1] + arr[i]
return prefix_sum
public class PrefixSumArray {
public static int[] constructPrefixSumArray(int[] arr) {
int n = arr.length;
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i — 1] + arr[i];
}
return prefixSum;
}
public static void main(String[] args) {
int[] inputArray = {3, 1, 5, 2, 4};
int[] prefixSumArray = constructPrefixSumArray(inputArray);
for (int num : prefixSumArray) {
System.out.print(num + “ “);
}
}
}
#include <iostream>
#include <vector>
std::vector<int> constructPrefixSumArray(std::vector<int>& arr) {
int n = arr.size();
std::vector<int> prefixSum(n);
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i — 1] + arr[i];
}
return prefixSum;
}
int main() {
std::vector<int> inputArray = {3, 1, 5, 2, 4};
std::vector<int> prefixSumArray = constructPrefixSumArray(inputArray);
for (int num : prefixSumArray) {
std::cout << num << “ “;
}
return 0;
}
Сложность времени и пространства
Временная сложность массива сумм префиксов составляет O(n), где n — размер входного массива. Это связано с тем, что мы проходим по входному массиву один раз, выполняя операцию с постоянным временем для каждого элемента, чтобы вычислить сумму префикса.
Объемная сложность массива сумм префиксов составляет O(n), где n – размер входного массива. Это связано с тем, что мы создаем дополнительный массив того же размера, что и входной массив, для хранения значений суммы префиксов.
Заключение
Массив сумм префиксов служит мощным инструментом для оптимизации вычислений с кумулятивными суммами. Создав массив сумм префиксов, мы можем эффективно отвечать на запросы, связанные с суммами диапазонов, суммами подмассивов и вычислениями средних значений. Возможность выполнять эти вычисления за постоянное время приводит к значительному повышению производительности, особенно для больших наборов данных. Понимание и использование потенциала массивов сумм префиксов дает нам ценную технику для более эффективного решения вычислительных задач.
Итак, в следующий раз, когда мы столкнемся с проблемами, требующими вычисления кумулятивных сумм, подумайте об использовании возможностей массивов сумм префиксов. Используя эту технику, мы можем открыть новые уровни эффективности и улучшить свои навыки решения проблем в мире алгоритмов и структур данных.
