Временная сложность
O(n)
Массив префиксных сумм предварительно обрабатывает статический массив, чтобы запросы суммы на отрезке выполнялись за O(1). В каждой позиции хранится сумма всех элементов до соответствующего индекса включительно.
Как это работает:
1. Инициализировать prefix[0] = arr[0]
2. Для каждого следующего индекса прибавлять текущее значение к предыдущей префиксной сумме
3. Вычислять sum(l, r) по формуле prefix[r] - prefix[l - 1]
4. Если l = 0, результатом будет просто prefix[r]
Временная сложность: O(n) на предварительную обработку, O(1) на каждый запрос
Пространственная сложность: O(n)
Лучше всего подходит, когда:
- Массив является статическим
- Требуется выполнять множество запросов суммы на отрезке
- Вы хотите потратить время на один проход предварительной обработки ради мгновенных ответов на запросы
Ограничение:
- Точечные обновления здесь не обрабатываются эффективно; для динамических обновлений используйте другие структуры данных, например дерево Фенвика (Fenwick Tree) или дерево отрезков (Segment Tree).
Похожие алгоритмы
Частые вопросы
- Что такое Массив префиксных сумм?
- Массив префиксных сумм предварительно обрабатывает статический массив, чтобы запросы суммы на отрезке выполнялись за O(1). В каждой позиции хранится сумма всех элементов до соответствующего индекса включительно.
- Какова сложность Массив префиксных сумм?
- Время (среднее): O(n) · Память: O(n)
- Для кого предназначена визуализация Массив префиксных сумм?
- Визуализация Массив префиксных сумм рассчитана на начальный уровень в категории «Основы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Массив префиксных сумм?
- В той же категории (Основы) вы можете изучить: Big O Notation, Recursion, Two Pointers. Каждый из них имеет интерактивную визуализацию.