Дерево Фенвика

Дерево Фенвика Бинарное индексированное дерево
Тип	Биномиальное дерево
Изобретенный	1989
Изобретён	Boris Ryabko
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск О(логарифм n ) О(логарифм n ) Вставлять О(логарифм n ) О(логарифм n ) Пространственная сложность Космос На ​ ) На ​ )

Дерево Фенвика или двоично-индексированное дерево (BIT) — это структура данных, которая может эффективно обновлять значения и вычислять суммы префиксов в массиве значений.

Эту структуру предложил Борис Рябко в 1989 году. с дальнейшей модификацией, опубликованной в 1992 году. Впоследствии оно стало известно под названием «дерево Фенвика» в честь Питера Фенвика, который описал эту структуру в своей статье 1994 года.

По сравнению с плоским массивом значений дерево Фенвика обеспечивает гораздо лучший баланс между двумя операциями: обновлением значения и вычислением суммы префикса. Плоский массив $n$ значения могут хранить либо значения, либо суммы префиксов. В первом случае вычисление сумм префиксов требует линейного времени; во втором случае обновление значений массива требует линейного времени (в обоих случаях другая операция может выполняться за постоянное время). Деревья Фенвика позволяют выполнять обе операции в $O(\log n)$ время. Это достигается путем представления значений в виде дерева с $n+1$ узлы, где значение каждого узла в дереве представляет собой префиксную сумму массива от индекса родительского узла (включительно) до индекса узла (исключающего). Само дерево является неявным и может храниться как массив $n$ значения, при этом неявный корневой узел опущен из массива. Древовидная структура позволяет выполнять операции поиска значения, обновления значения, суммы префикса и суммы диапазона, используя только $O(\log n)$ доступ к узлу.

Мотивация

Основная статья: Префиксные суммы § Приложения

Учитывая массив значений, иногда желательно вычислить промежуточную сумму значений до каждого индекса в соответствии с некоторой ассоциативной двоичной операцией (сложение целых чисел является наиболее распространенным). Деревья Фенвика предоставляют метод запроса промежуточной суммы по любому индексу или сумме префикса, а также позволяют вносить изменения в базовый массив значений и позволяют всем дальнейшим запросам отражать эти изменения.

Деревья Фенвика специально разработаны для реализации алгоритма арифметического кодирования , который поддерживает подсчет каждого произведенного символа и должен преобразовать его в кумулятивную вероятность того, что символ меньше заданного символа. Развитие операций, которые он поддерживает, было в первую очередь мотивировано использованием в этом случае.

Описание

Дерево Фенвика — это неявное дерево , в котором узлы пронумерованы последовательно, а отношения «родитель-потомок» определяются арифметическими действиями по индексам узлов.

Важной функцией в этой арифметике индексов является младший бит набора , также называемый операцией поиска первого набора . Это наибольшая степень двойки, которая делит индекс $i$. Это степень двойки (1, 2, 4, 8, ...), а не показатель степени (0, 1, 2, 3, ...). Его можно эффективно вычислить в с дополнением до двух как арифметике $\operatorname {lsb} (i)=i\mathbin {\&} -i$ (где & обозначает побитовое И ).

Дерево Фенвика легче всего понять, используя массив, основанный на единице. $A[n]$ с $n$ ценности. Используя синтаксис полуоткрытого интервала , пусть $A(i,j]=\{A[k]\}_{k=i+1}^{j},$ диапазон от $i$ (эксклюзивный) для $j$ (включительно). Соответствующий массив Фенвика $F[n]$ сохраняет суммы диапазонов $\textstyle F[i]=\sum A(i-\operatorname {lsb} (i),i]$. То есть сумма $\operatorname {lsb} (i)$ значения, заканчивающиеся на и включая $A[i]$.

В некоторых описаниях используется фиктивный узел 0, но на самом деле к нему никогда не обращаются, и его не нужно явно сохранять. $\operatorname {lsb} (0)=\infty ,$ но значение никогда на самом деле не требуется. $F[0]$ можно считать содержащим сумму пустого диапазона $A(0,0]=\{\}$ со значением 0.

«Дерево Фенвика» на самом деле представляет собой три неявных дерева в одном и том же массиве: дерево опросов, используемое для перевода индексов в суммы префиксов, дерево обновления , используемое для обновления элементов, и дерево поиска для перевода сумм префиксов в индексы (ранговые запросы). Первые два обычно идут вверх, а третий обычно идет вниз.

Дерево допросов

Дерево опросов определяется таким образом, что родительский элемент узла $i$ является $i-\operatorname {lsb} (i)=i\mathbin {\&} (i-1)$. Например, родительским элементом 6 = 110 ₂ является 4 = 100 ₂ . Неявный узел 0 является корнем.

Каждый уровень $k$ дерева содержит узлы с индексами, соответствующими суммам $k$ различные степени двойки (с $k=0$ представляющая пустую сумму 0). Например, уровень $k=1$ содержит узлы $1=2^{0},2=2^{1},4=2^{2},...$ и уровень $k=2$ содержит узлы $3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...$

Узел $i$ имеет $\log _{2}(\operatorname {lsb} (i))$ дети ( $i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2$), и $\operatorname {lsb} (i)$ все потомки. (Эти числа включают узлы, превышающие $n$, которые опущены и к которым никогда не обращаются.)

На диаграмме ниже показана структура дерева запросов дерева Фенвика из 16 узлов, включая корень, поэтому оно соответствует массиву A из 15 элементов:

Изображение 16-узлового дерева опросов Фенвика, содержащего суммы диапазонов 15-узлового массива A.

Чтобы найти сумму префикса $A[1]+\cdots +A[i]$, суммируем значения в $i$, его родительский элемент, родительский элемент его родительского элемента и т. д. до корня (но не включая его). Чтобы вычислить сумму диапазона $A[i]+\cdots +A[j]$, вычтите суммы префиксов для $i-1$ и $j$. Это можно оптимизировать, остановившись на их первом общем предке.

Дерево обновлений

Дерево обновлений является зеркальным отражением дерева опросов. Родитель узла $i$ является $i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1$ (где | обозначает побитовое ИЛИ ). Например, родительским элементом 6 = 110 ₂ является 8 = 1000 ₂ .

Это концептуальное дерево бесконечно, но только часть с индексами до $n$ хранится или используется. Исключение фиктивных узлов с индексами больше $n$ это будет лес непересекающихся деревьев, по одному на каждый бит, заданный в двоичном представлении $n$.

Здесь предками узла являются все узлы, суммы диапазонов которых включают его собственные. Например, $F[6]$ содержит сумму $A(4,6]$, $F[8]$ содержит сумму $A(4,8]$, и так далее.

Чтобы изменить одно из значений $A[i]$, добавьте изменение в $F[i]$, затем $i$родительский элемент, затем его дедушка и бабушка и так далее, пока индекс не превысит $n$.

Дерево поиска

В отличие от двух других деревьев, дерево поиска представляет собой двоичное дерево , расположенное в порядке, который Кнут называет «боковой кучей». Каждому узлу присваивается высота, равная количеству конечных нулей в двоичном представлении его индекса, при этом родительский и дочерний узлы являются ближайшими по числовому значению индексами соседней высоты. Узлы с нечетными индексами ( $\operatorname {lsb} (i)=1$) — листья. Узлы с четными индексами имеют два ближайших узла следующего наименьшего индекса в качестве дочерних. $i\pm \operatorname {lsb} (i)/2$. Узел $i$родителем в дереве поиска является $(i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))$.

Например, дочерними элементами 6 = 110 ₂ являются 5 = 101 ₂ и 7 = 111 ₂ , а родительским — 4 = 100 ₂ .

Хотя это дерево потенциально бесконечно, мы можем определить его корень как самый высокий из существующих узлов, индекс которого равен наибольшей степени 2, меньшей или равной $n$.

Узел может иметь фиктивного родителя с индексом больше, чем $n$ но у меня все еще есть бабушка и дедушка. Если приведенный выше пример применим к дереву из 5 узлов, то узел 5 будет иметь фиктивного родителя 6, но уже существующего прародителя 4.

Дерево поиска можно рассматривать как комбинацию двух предыдущих деревьев. Левое поддерево узла содержит всех его потомков в дереве обновлений, а его правое поддерево содержит всех его потомков в дереве опросов. Родителем узла в дереве поиска является либо его родительский элемент запроса, либо родительский элемент обновления (в зависимости от того, является ли узел правым или левым дочерним элементом соответственно), а родительский элемент другого типа может быть найден несколькими шагами вверх в дереве поиска.

Однако обходы вверх по дереву поиска встречаются редко; его основное использование — выполнение ранговых запросов: учитывая сумму префикса, под каким индексом она появляется? Это делается путем вниз обхода дерева поиска . Во время обхода поддерживаются три переменные: индекс текущего узла, искомый ранг в поддереве, корнем которого является текущий узел, и «резервный индекс», который возвращается, если искомый ранг больше, чем можно найти в поддереве.

Первоначально текущий узел является корнем, искомый ранг — исходным запросом, а резервный индекс — специальным значением «переполнения», указывающим, что ранг отсутствует в дереве. (В зависимости от приложения, $0$ или $n+1$ можно использовать для этой цели.)

На каждом шаге, либо текущий узел является фиктивным узлом (индекс больше $n$), или мы должны решить, находится ли искомая позиция слева или справа от конца текущего узла. Если искомый ранг меньше значения массива Фенвика $F[i]$ для текущего узла мы должны найти его левое поддерево. Если оно больше, ищите его правое поддерево. Если оно равно, выбранное направление зависит от того, как вы хотите обрабатывать поиск сумм, лежащих точно между двумя узлами.

Эти три возможности затем делятся в зависимости от того, является ли текущий узел листом или нет:

• Если текущий узел является листом и:
  • цель находится в его (пустом) левом поддереве, верните текущий индекс.
  • оно фиктивное или цель находится в правом поддереве, верните резервный индекс.
• Если текущий узел не является листом и:
  • это фиктивно, искать тот же ранг в его левом поддереве с неизменным запасным индексом.
  • цель находится в его левом поддереве, найдите тот же ранг в его левом поддереве с текущим индексом в качестве резервного индекса.
  • цель находится в правом поддереве, найдите целевой ранг минус значение текущего узла в правом поддереве с неизмененным резервным индексом.

Псевдокод

Простая реализация на псевдокоде двух основных операций над деревом Фенвика — запроса и обновления — выглядит следующим образом:

function query(tree, index) is
    sum := 0
    while index > 0 do
        sum += tree[index]
        index -= lsb(index)
    return sum

function update(tree, index, value) is
    while index < size(tree) do
        tree[index] += value
        index += lsb(index)

Функция ${\text{lsb}}(n)$ вычисляет младший значащий 1-⁠бит или последний установленный бит данного $n$ или, что то же самое, наибольшая степень двойки , которая также является делителем $n$. Например, ${\text{lsb}}(20)=4$, как показано в его двоичном представлении: ${\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4$. Эту функцию можно просто реализовать в коде посредством побитовой операции И : lsb(n) = n & (-n), предполагая целочисленный тип данных со знаком .

Строительство

Один простой алгоритм построения дерева Фенвика состоит из инициализации дерева нулевыми значениями и индивидуального обновления каждого индекса. Это решение работает в $O(n\log {n})$ время, но $O(n)$ возможно строительство:

function construct(values) is
    tree := values
    for every index, value in tree do
        parentIndex := index + lsb(index)
        if parentIndex < size(tree) then
            tree[parentIndex] += value
    return tree

См. также

• Дерево статистики заказа
• Префиксные суммы
• Дерево сегментов

Внешние ссылки

• Учебное пособие по деревьям Фенвика на TopCoder
• Статья о деревьях Фенвика на сайте Algorithmist
• Запись о деревьях Фенвика на вики Polymath.
• обмен стеками