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

редактировать

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

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

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

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

Содержание

1 Мотивация
2 Описание
3 Реализация
4 Обновление и запрос дерева
5 См. Также
6 Ссылки
7 Внешние ссылки

Мотивация

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

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

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

Деревья Фенвика могут быть расширены для обновления и запроса подмассивов многомерных массивов. Эти операции могут выполняться со сложностью $O (4 d log d ⁡ n) {\ displaystyle O (4 ^ {d} \ log ^ {d} n)}$ ${\ displaystyle O (4 ^ {d} \ log ^ {d} n)}$ , где $d {\ displaystyle d}$ $d$ - количество измерений, а $n {\ displaystyle n}$ $n$ - количество элементов по каждому измерению.

Описание

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

Начальный процесс построения дерева Фенвика по таблице значений выполняется за $O (n) {\ displaystyle O (n)}$ $O (n)$ времени. Другие эффективные операции включают поиск индекса значения, если все значения положительны, или всех индексов с заданным значением, если все значения неотрицательны. Также поддерживается масштабирование всех значений на постоянный коэффициент за $O (n) {\ displaystyle O (n)}$ $O (n)$ времени.

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

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

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

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

Реализация

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

#define LSB (i) ((i) - (i)) // обнуляет все биты, кроме самого младшего // Предполагается индексирование на основе единицы int A [SIZE + 1]; int sum (int i) // Возвращает сумму от индекса 1 до i {int sum = 0; while (i>0) sum + = A [i], i - = LSB (i); сумма возврата; } void add (int i, int k) // Добавляет k к элементу с индексом i {while (i <= SIZE) A[i] += k, i += LSB(i); }

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

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

Комбинация операций с двоичным индексированным деревом и соответствующий алгоритм
Код типа теста	Операция обновления	Операция запроса	Алгоритм	Соответствующие API для выполнения	Комментарий	Пример
1	Обновление точки	Точечный запрос (частота)	Обновление и запрос в одном массиве BIT	Обновление (BIT1, индекс, значение) Запрос (BIT1, индекс) - запрос (BIT1, index-1)	Альтернатива 1: запрос (индекс) с использованием метода общего предка. Альтернатива 2: на этот запрос можно ответить за время O (1), обменявшись на пространство O (n).	A = [1 2 3 4 5]; Обновление (2, 3) = [1 5 3 4 5] Запрос (2) = 5, Запрос (3) = 3
2	Точка Обновление	Точечный запрос (совокупная частота)	Обновление и запрос в одном массиве 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, index, value) для (индекса от L до R) { Запрос (BIT1, индекс) - Запрос (BIT1, index-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, индекс, значение). Запрос (BIT1, R) - запрос (BIT1, L - 1)		А = [1 2 3 4 5]; Обновление (2, 3) = [1 5 3 4 5] Запрос (2, 4) = Запрос (4) - Запрос (1) = 12
5	Обновление диапазона	Запрос точки (Частота)	Обновление и запрос на двух массивах BIT Диапазон = [L, R]	Обновление (BIT1, L, значение) Обновление (BIT1, R + 1, -значение) Обновление (BIT2, L, (L-1) * значение) Обновление (BIT2, R + 1, -value * R) Запрос (BIT1, BIT2, index) - Query (BIT1, BIT2, index-1)	Техника операции 1 здесь не применяется.. Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)	A = [1 2 3 4 5]; Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2) = 5, Запрос (3) = 6
6	Обновление диапазона	Запрос точки (совокупный Частота)	Обновление и запрос на двух массивах BIT Диапазон = [L, R]	Обновление (BIT1, L, значение) Обновление (BIT1, R + 1, -значение) Обновление (BIT2, L, (L-1) * значение) Обновление (BIT2, R + 1, -value * R) Запрос (BIT1, BIT2, индекс)	Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)	A = [1 2 3 4 5]; Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2) = 6, Запрос (3) = 12
7	Обновление диапазона	Запрос диапазона (Частота)	Обновление и запрос к двум массивам BIT Выполнение операции 1 для каждого индекса в диапазоне Range = [L, R]	Обновление (BIT1, L, значение) Обновление (BIT1, R + 1, -значение) Обновление (BIT2, L, (L-1) * значение) Обновление (BIT2, R + 1, -значение * R) for (индекс от L до R) { Запрос (BIT1, BIT2, index) - Запрос (BIT1, BIT2, index-1) }	Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - сумма (BIT2, index)	A = [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, -value * R) Запрос (BIT1, BIT2, R) - Запрос (BIT1, BIT2, L-1)	Запрос (BIT1, BIT2, index) = index * sum (BIT1, index) - sum (BIT2, index)	A = [1 2 3 4 5]; Обновление (2, 4, 3) = [1 5 6 7 5] Запрос (2, 4) = Запрос (4) -Query (1) = 18

См. Также

Литература

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

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

Учебник по деревьям Фенвика на TopCoder
Статья о деревьях Фенвика по алгоритму
обмен стеком