Дерево Фенвика
Описание структуры
Дерево Фе́нвика (англ. Binary indexed tree) — структура данных, требующая памяти и позволяющая эффективно (за ) выполнять следующие операции:
- изменять значение любого элемента в массиве,
- выполнять некоторую ассоциативную, коммутативную, обратимую операцию на отрезке .
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив . Деревом Фенвика будем называть массив из элементов: , где и — некоторая функция, от выбора которой зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать операции вставки и изменения элемента за время . Она задается простой формулой: , где — это операция побитового логического . При числа и его значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.
Эту функцию можно вычислять по другой формуле: где — количество подряд идущих единиц в конце бинарной записи числа . Оба варианта равносильны, так как функция, заданная какой-либо из этих формул, заменяет все подряд идущие единицы в конце числа на нули.
Запрос изменения элемента
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменяется массив при изменении элемента .
| Лемма: |
Для пересчёта дерева Фенвика при изменении величины необходимо изменить элементы дерева , для индексов которых верно неравенство . |
| Доказательство: |
| необходимо менять те , для которых попадает в необходимые удовлетворяют условию . |
| Лемма: |
Все такие , для которых меняется при изменении , можно найти по формуле , где — это операция побитового логического . |
| Доказательство: |
| Из доказанной выше леммы следует, что первый элемент последовательности само . Для него выполняется равенство, так как . По формуле мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как осталось прежним или уменьшилось, а увеличилось. не может увеличится, так как функция заменяет последние подряд идущие единицы числа на нули, а по формуле у нового значения увеличивается количество единиц в конце, что не может привести к увеличению . Докажем от противного, что нельзя рассматривать значения , отличные от тех, которые мы получили по формуле. Рассмотрим две различные последовательности индексов. Первая последовательность получена по формуле, вторая — некоторая последовательность чисел, не превосходящие . Возьмём число из второй последовательности, которого нет в первой последовательности. Пусть . Уберём у все подряд идущие единицы в конце двоичной записи, столько же цифр уберём в конце числа . Обозначим их как и . Чтобы выполнялось условие , должно выполняться неравенство . Но если , то и , что противоречит условию . Значит, . Но тогда возможно получить по формуле , следовательно, . Получили противоречие: можно вычислить по формуле, а это значит, что оно содержится в первой последовательности. Таким образом, нужные элементы можно искать по формуле . |
Заметим, что возрастает немонотонно. Поэтому нельзя просто перебирать значения от , пока не нарушается условие. Например, пусть . При данной стратегии на следующем шаге () нарушится условие и мы прекратим пересчитывать . Но тогда мы упускаем остальные значения , например .
| , десятичная запись | |||||||||||
| , двоичная запись | |||||||||||
| , двоичная запись | |||||||||||
| , десятичная запись |
Все мы можем получить следующим образом: . Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию . Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.
Несложно заметить, что данная последовательность строго возрастает и в худшем случае будет применена логарифм раз, так как добавляет каждый раз по одной единице в двоичном разложении числа .
Напишем функцию, которая будет прибавлять к элементу число , и при этом меняет соответствующие частичные суммы. Так как наш массив содержит элементов, то мы будем искать до тех пор, пока оно не превышает значение .
function modify(i, d):
while i < N
t[i] += d
i = i | (i + 1)
Часто можно встретить задачу, где требуется заменить значение элемента на . Заметим, что если вычислить разность и , то можно свести эту задачу к операции прибавления к .
function set(i, x): d = x - a[i] modify(i, d)
Построение дерева можно осуществить, исходя из его описания. Но можно быстрее, если использовать функцию modify для каждого элемента массива . Тогда мы получим время работы .
function build():
for i = 0 to N - 1
modify(i, a[i])
Запрос получения значения функции на префиксе
Пусть существует некоторая бинарная операция . Чтобы получить значение на отрезке , нужно провести операцию, обратную к , над значениями на отрезках и .
В качестве бинарной операции рассмотрим операцию сложения.
Обозначим . Тогда .
Для нахождения будем действовать следующим образом. Берём , которое является суммой элементов с индексами от до . Теперь к этому значению нужно прибавить . Аналогично продолжаем складывать, пока не не станет равным .
Покажем, что запрос суммы работает за . Рассмотрим двоичную запись числа . Функция заменила его последние единицы на нули (заметим, что количество нулей в конце станет больше, чем количество единиц в конце до этого). Теперь вычтем единицу из (переход к следующему столбику). Количество единиц в конце увеличилось, по сравнению с , так как мы заменили все нули в конце на единицы. Проводя эти действия дальше, мы придём к тому, что получили . В худшем случае мы должны были повторять эти операции раз, где — количество цифр в двоичной записи числа , что не превосходит . Значит, запрос суммы выполняется за .
Реализация
Приведем код функции :
int sum(i):
result = 0;
while f(i) >= 0
result += t[i]
i = f(i) - 1
Сравнение дерева Фенвика и дерева отрезков
- Дерево Фенвика занимает в константное значение раз меньше памяти, чем дерево отрезков. Это следует из того, что дерево Фенвика хранит только значение операции для каких-то элементов, а дерево отрезков хранит сами элементы и частичные результаты операции на подотрезках, поэтому оно занимает как минимум в два раза больше памяти.
- Дерево Фенвика проще в реализации.
- Операция на отрезке, для которой строится дерево Фенвика, должна быть обратимой, а это значит, что минимум (как и максимум) на отрезке это дерево считать не может, в отличие от дерева отрезков. Но если нам требуется найти минимум на префиксе, то дерево Фенвика справится с этой задачей. Такое дерево Фенвика поддерживает операцию уменьшения элементов массива. Пересчёт минимума в дереве происходит быстрее, чем обновление массива минимумов на префиксе.
