Дерево Фенвик
-
Основы дерева Фенвика
- Дерево Фенвика — это структура данных для эффективного вычисления сумм префиксов и диапазонов в массиве.
- Оно состоит из трех типов деревьев: дерево запросов, дерево обновлений и дерево поиска.
-
Дерево запросов
- Используется для вычисления суммы префикса, суммируя значения в диапазоне от 1 до i.
- Оптимизировано путем суммирования значений в диапазоне от 1 до корня, исключая корень.
-
Дерево обновлений
- Отражает дерево запросов, родительский элемент узла i равен i + лсб(i).
- Хранит только часть дерева, соответствующую индексам до n, с фиктивными узлами для индексов выше n.
-
Дерево поиска
- Представляет собой бинарное дерево с узлами, упорядоченными по высоте, где узлы с нечетными индексами являются листьями.
- Используется для выполнения ранговых запросов, поддерживая три переменные: индекс, ранг и резервный индекс.
-
Псевдокод
- Описывает операции запроса и обновления в дереве Фенвика.
-
Построение дерева Фенвика
- Один из алгоритмов построения дерева Фенвика инициализирует его нулями и обновляет каждый индекс отдельно.
- Существует более быстрое решение, требующее
- O
- (
- n
- )
- {\displaystyle O(n)}
- времени построения.