Дерево Фенвика или BITree - очень популярная структура данных, которая в основном используется для решения вопросов запроса диапазона. Особенность дерева Фенвика заключается в том, что оно может вычислять значения любой функции f в заданном диапазоне [1: г] т.е.

f (arr [1], arr [l + 1],.. arr [r-1], arr [r])

Если f - обратимая функция, мы можем вычислить ее для любого диапазона [l: r].

Чтобы понять BITree, мы рассмотрим один из самых основных вопросов и рассмотрим f как функцию, которая вычисляет сумму элементов.

Вопрос:

Вам дан массив arr [1… n]. Вам будут заданы несколько запросов, которые могут быть двух типов:

  1. Для индекса x найдите сумму элементов в массиве от индекса 1 до индекса x (включительно).
  2. Учитывая индекс x и значение val, добавьте значение к arr [x].

Решение:

Тривиальным решением было бы выполнить операцию обновления в O (1) и для вычисления суммы элементов просто запустить цикл в O (N). Или вы можете иметь массив префиксов, в котором будет храниться сумма префиксов, с его помощью вы можете отвечать на запросы в O (1), но обновление займет O (N) . Чтобы решить эту проблему, мы увидим, как мы можем использовать структуру данных BITree, которая поддерживает как обновление, так и операцию запроса в O (log (N)), где N - размер массива.

Интуиция:

Основная идея BITree заключается в том, что любое число может быть представлено как сумма степеней двойки. Таким же образом мы можем выразить диапазон (от 1 до x) как сумма других последовательных поддиапазонов (которые хранятся в размерах степеней двойки). Будет более понятно, если вы прочитаете следующий абзац и увидите диаграмму.

Рассмотрим массив (обратите внимание, что массив считается основанным на 1):

Как работает BITree, при любом индексе idx дерева сохраняемое значение будет суммой значений от idx -2 ^ r + 1 до idx (включительно). Здесь r представляет позицию младшего бита idx. В BITree idx 0 хранится в нуле.

Пример: рассмотрим индекс 6, его двоичное представление будет 110. Младший значащий бит набора находится в позиции 1. Таким образом, BIT [6] хранит информацию о диапазоне от 6 - 2¹ + 1 = 5 до 6. Точно так же для всех индексы, которые мы можем вычислить и построить следующую таблицу, которая сообщит, какие значения хранятся в этих индексах:

Из приведенной диаграммы довольно ясно, как данные хранятся в дереве. Теперь предположим, что нам нужно найти сумму для диапазона от 1 до 7. На диаграмме эту сумму диапазона можно выразить как BIT [7] + BIT [6] + BIT [4]. Если мы представим эти числа в двоичном формате, то увидим, что 7 - это 111, 6 - 110, а 4 - 100. Точно так же сумма для диапазона от 1 до 9 будет БИТ [9] + БИТ [8]. 9 и 8 в двоичной форме будут 1001 и 1000 соответственно. Мы постоянно удаляем крайний правый установленный бит и добавляем эти значения, чтобы получить окончательный ответ.

Вам может быть интересно, почему это называется деревом. Причина в том, что больший сегмент считается родительским для меньшего (полностью внутри него). Чтобы перейти к родительскому сегменту, мы выполняем idx + (idx & -idx) [Многократное добавление LSB]. Мы можем сделать наоборот и пойти к детям.

Реализация:

Примечание: реализация BITree выполняется на C ++. Большинство функций не принимают BIT или arr в качестве аргумента, учтите, что обе они объявлены глобально как массив, размер BIT равен N + 1, а массив равен N. Это не лучший способ объявлять их как global, а затем использовать их, правильным способом было бы создать класс или структуру для Fenwick Tree. Массив и запросы основаны на нулевом индексе. Соответствующую полную реализацию можно найти здесь.

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

Любое число можно рассматривать в форме: (pre) 1 (нули), где часть pre - это биты слева от самого правого установленного бита. Пример: 10001100, число может быть представлено как (10001) до 1 (00) нулей.

Отрицательное значение любого числа хранится как ~ (num) + 1. Символ ~ представляет собой обращение всех нулей к единицам и единиц к нулям. Таким образом, отрицание (pre) 1 (нулей) станет (отрицанием pre) 0 (единицами). После прибавления к нему 1 оно становится (отрицательным от пред) 1 (нулями). Теперь, если вы, это и исходное число, останется только самый правый установленный бит, а остальные станут 0.

число, сохраненное в форме дополнения 2, становится следующим:

10001100 = ( 01110011 + 1) = 01110100

и их объединение приводит к
10001100 & 01110100 = 00000100

Теперь мы готовы закодировать BITree.

Сумма диапазона:

Как уже обсуждалось, продолжайте удалять младший бит и добавлять значения по этому индексу в дереве, чтобы получить сумму.

Если заданный вход равен 5, то BIT [5] (итерация 1) + BIT [4] (итерация 2) будет возвращена как сумма. Цикл удалит крайний правый установленный бит до тех пор, пока idx не перестанет иметь установленных битов. Следовательно, временная сложность будет равна количеству битов, равному log (N). Следовательно, сумму можно вычислить в O (log (N)).

Обновление точки:

Чтобы выполнить обновление дерева, просто продолжайте добавлять значение ко всем сегментам, где находится эта точка. Операция прямо противоположна операции суммирования:

Здесь N обозначает максимальный размер Дерева или запрашиваемого индекса, то есть размер массива. Рассмотрим обновление idx 5. Значение idx изменится с 5 на 6, затем на 8, затем на 16 (здесь мы остановимся, потому что размер нашего массива всего 10).

Здесь idx обновляется до тех пор, пока idx не станет больше, чем N. Добавляется младший значащий бит, поэтому временная сложность операции обновления равна O (log (N)).

Здание:

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

Сложность построения дерева составляет O (N * log N).

Ответ для заданного диапазона:

Ответ на запросы для любого заданного диапазона [l: r] мы можем просто использовать

сумма [r] - сумма [l - 1]

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

Расширение его до 2D-массива:

BITrees можно использовать для получения совокупной суммы элементов для данной матрицы. Под совокупной суммой здесь понимается сумма всех элементов arr [i] [j] таких, что 1 ≤ i ≤ x и 1 ≤ j ≤ y. Ниже приведен код для получения суммы элементов в матрице от [1: 1] до [x: y ]

Сумма двухмерного диапазона:

Обновление точек в 2D:

Сложность обоих будет O (log (N) * log (M)). Где N представляет количество строк, а M представляет количество столбцов.

Варианты BITree:

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

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

Здесь обновление добавления val в диапазон от l до r выполняется как добавить + val к l, и добавить -val на r + 1. Возьмите кумулятивную сумму от 1 до N, вы заметите, что обновленное значение будет на картинке, только когда вы находитесь в диапазоне от l до r. Мы используем это наблюдение, чтобы ответить на вопросы об обновлении диапазона и запросе точки. Приведенный ниже код к настоящему времени должен быть достаточно очевидным.

2. Запрос диапазона и обновление диапазона

Чтобы выполнить обновление диапазона, нам сначала нужно получить некоторые наблюдения. Предположим, вы добавили val из индекса между l до r. Изначально весь массив был нулевым. Таким образом, после этой операции обновления сумма от 1 до некоторого idx может быть записана как

Его можно переписать как:

Мы используем два BITree. BIT1 имеет обновление + x на l и -x на r + 1 (так же, как обновление диапазона и запрос точки). Но здесь у нас есть дополнительный термин, чтобы удалить этот дополнительный термин, мы используем BIT2, это обновление + val * (l-1) для l и -val * (r) для r + 1.

Заключение

  1. Дерево Фенвика требует O (n) памяти и O (log (N)) для обновления диапазона и запроса.
  2. Дерево Фенвика в основном используется для запроса диапазона и обновления точки, но в зависимости от функции оценки оно может быть изменено для обновления диапазона.
  3. Его очень легко реализовать, и его можно расширить до n измерений.
  4. Дерево Фенвика быстрее, чем дерево сегментов, но не так мощно, как дерево сегментов.
  5. Он может давать только кумулятивные значения, для получения запроса диапазона должна существовать обратная операция, иначе реализация станет утомительной.

Источник

  1. Https://cp-algorithms.com/data_structures/fenwick.html
  2. Https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/
  3. Https://en.wikipedia.org/wiki/Fenwick_tree

В конце ссылки 1 есть несколько хороших проблем, которые нужно решить.

Если хотите узнать о деревьях сегментов :)