Дерево фенвик - Fenwick tree

Создайте двоичное индексированное дерево для массива [1, 2, 3, 4, 5], вставляя их по одному.

А Дерево фенвик или же двоичное индексированное дерево это структура данных, которая может эффективно обновлять элементы и вычислять префиксные суммы в таблице чисел.

Эта структура была предложена Борисом Рябко в 1989 году. [1]с последующей модификацией, опубликованной в 1992 году.[2]Впоследствии он стал известен под названием Фенвикское дерево после Питер Фенвик который описал эту структуру в своей статье 1994 года.[3]

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

Мотивация

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

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

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

Используя дерево Фенвика, требуется только операции для вычисления любой желаемой совокупной суммы или, в более общем смысле, суммы любого диапазона значений (не обязательно начиная с нуля).

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

Описание

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

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

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

Чтобы найти сумму любого заданного индекса, рассмотрите двоичное расширение индекса и добавьте элементы, которые соответствуют каждому 1 биту в двоичной форме.

Например, предположим, что кто-то хочет найти сумму первых одиннадцати значений. Одиннадцать - это 10112 в двоичном формате. Он содержит три бита 1, поэтому необходимо добавить три элемента: 10002, 10102, и 10112. Они содержат суммы значений 1–8, 9–10 и 11 соответственно.

Чтобы изменить одиннадцатое значение, необходимо изменить элементы 1011.2, 11002, 100002, и все более высокие степени 2 до размера массива. Они содержат суммы значений 11, 9–12 и 1–16 соответственно. Максимальное количество элементов, которые могут нуждаться в обновлении, ограничено количеством битов в размере массива.

Выполнение

Далее следует простая реализация C.

#define LSB (i) ((i) & - (i)) // обнуляет все биты, кроме младшего// Предполагается одно основанное индексированиеint А[РАЗМЕР+1];int сумма(int я) // Возвращает сумму от индекса 1 до i{    int сумма = 0;    пока (я > 0)         сумма += А[я], я -= LSB(я);    возвращаться сумма;} пустота Добавить(int я, int k) // Добавляет k к элементу с индексом i{    пока (я <= РАЗМЕР)         А[я] += k, я += LSB(я);}

Обновление и запрос дерева

В следующей таблице описаны различные способы использования дерева Фенвика. Что еще более важно, в нем указывается правильный API, который нужно вызывать или использовать для достижения желаемого результата, а также пример, объясняющий вариант использования.

Комбинация операций двоичного индексированного дерева и соответствующий алгоритм
Код типа тестаОперация обновленияОперация запросаАлгоритмСоответствующие API для выполненияКомментарийПример
1Обновление точкиPoint Query

(Частота)

Обновление и запрос в одном массиве BITОбновление (BIT1, индекс, значение)

Запрос (BIT1, индекс) - Запрос (BIT1, индекс-1)

Альтернатива 1: запрос (индекс) с использованием метода общих предков.

Альтернатива 2: на этот запрос можно ответить за O (1) время, потратив на O (n) пространство.

А = [1 2 3 4 5];

Обновление (2, 3) = [1 5 3 4 5] Запрос (2) = 5, Запрос (3) = 3

2Обновление точкиPoint Query

(Накопленная частота)

Обновление и запрос в одном массиве BITОбновление (BIT1, индекс, значение)

Запрос (BIT1, индекс)

А = [1 2 3 4 5];

Обновление (2, 3) = [1 5 3 4 5] Запрос (2) = 6, Запрос (3) = 9

3Обновление точкиЗапрос диапазона

(Частота)

Обновление и запрос в одном массиве BIT

Выполните операцию 1 для каждого индекса в диапазоне Range = [L, R]

Обновление (BIT1, индекс, значение)

для (индекс от L до R)

{

Запрос (BIT1, индекс) - Запрос (BIT1, индекс-1)

}

Это условие в идеале не интересно. Но его необходимо охватить, чтобы охватить все сценарии, а также придать этому сценарию одно конкретное значение.

Другие могут иметь собственное определение. На этот запрос можно ответить за O (k) время, обменявшись на O (n) пространство.

А = [1 2 3 4 5];

Обновление (2, 3) = [1 5 3 4 5] Запрос (2, 4) = [5 3 4]

4Обновление точкиЗапрос диапазона

(Накопленная частота)

Обновление и запрос в одном массиве BIT

Диапазон = [L, R]

Обновление (BIT1, индекс, значение)
Query (BIT1, R) - Запрос (BIT1, L - 1)		А = [1 2 3 4 5];

Обновление (2, 3) = [1 5 3 4 5] Запрос (2, 4) = Запрос (4) -Запрос (1) = 12

5Обновление диапазонаPoint Query

(Частота)

Обновление и запрос на двух массивах BIT

Диапазон = [L, R]

Обновить (BIT1, L, значение)

Обновить (BIT1, R + 1, -значение)

Обновить (BIT2, L, (L-1) * значение)

Обновление (BIT2, R + 1, -значение * R)

Запрос (BIT1, BIT2, index) - Запрос (BIT1, BIT2, index-1)

Техника операции 1 здесь не применяется.
Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)		А = [1 2 3 4 5];

Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2) = 5, Запрос (3) = 6

6Обновление диапазонаPoint Query

(Накопленная частота)

Обновление и запрос на двух массивах BIT

Диапазон = [L, R]

Обновить (BIT1, L, значение)

Обновить (BIT1, R + 1, -значение)

Обновить (BIT2, L, (L-1) * значение)

Обновление (BIT2, R + 1, -значение * R)

Запрос (BIT1, BIT2, индекс)

Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)А = [1 2 3 4 5];

Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2) = 6, Запрос (3) = 12

7Обновление диапазонаЗапрос диапазона

(Частота)

Обновление и запрос на двух массивах BIT

Выполните операцию 1 для каждого индекса в диапазоне

Диапазон = [L, R]

Обновить (BIT1, L, значение)

Обновить (BIT1, R + 1, -значение)

Обновить (BIT2, L, (L-1) * значение)

Обновление (BIT2, R + 1, -значение * R)

для (индекс от L до R)

{

Запрос (BIT1, BIT2, index) - Запрос (BIT1, BIT2, index-1)

}

Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)А = [1 2 3 4 5];

Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2, 4) = [5 6 7]

8Обновление диапазонаЗапрос диапазона

(Накопленная частота)

Обновление и запрос на двух массивах BIT

Диапазон = [L, R]

Обновить (BIT1, L, значение)

Обновить (BIT1, R + 1, -значение)

Обновить (BIT2, L, (L-1) * значение)

Обновление (BIT2, R + 1, -значение * R)

Запрос (BIT1, BIT2, R) - Запрос (BIT1, BIT2, L-1)

Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)А = [1 2 3 4 5];

Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2, 4) = Запрос (4) -Query (1) = 18

Смотрите также

Рекомендации

  1. ^ Борис Рябко (1989). «Быстрый он-лайн код» (PDF). Советская математика. Докл. 39 (3): 533–537.
  2. ^ Борис Рябко (1992). «Быстрый онлайн-адаптивный код» (PDF). IEEE Transactions по теории информации. 28 (1): 1400–1404.
  3. ^ Питер М. Фенвик (1994). «Новая структура данных для сводных таблиц частот». Программное обеспечение: практика и опыт. 24 (3): 327–336. CiteSeerX  10.1.1.14.8917. Дои:10.1002 / spe.4380240306.
  4. ^ Пушкар Мишра (2013). «Новый алгоритм обновления и запроса подмассивов многомерных массивов». arXiv:1311.6093. Дои:10.13140 / RG.2.1.2394.2485. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка