В двоичном индексированном дереве очень мало или относительно нет теории для изучения по сравнению с другими структурами данных. Единственное место, где он преподается лаконично - это учебник topcoder. Хотя учебник полностью во всех объяснениях, я не могу понять, что такое интуиция за таким деревом? И как доказать это правильность?
Я полагаю, что доказательство сложно объяснить. Итак, при использовании BIT, какой подход вы придерживаетесь?
Я нашел этот ответ от @templatetypedef очень четко объяснить интуицию и доказательство двоичного индексированного дерева: Ответ...
Интуитивно, вы можете представить двоичное индексированное дерево как сжатое представление двоичного дерева, которое само по себе является оптимизацией стандартного представления массива. Этот ответ приходит к одному возможному выводу.
Предположим, например, что вы хотите сохранить кумулятивные частоты для всего 7 разных элементов. Вы можете начать с написания семи ведер, в которые будут распределяться числа:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
Теперь предположим, что кумулятивные частоты выглядят примерно так:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
Используя эту версию массива, вы можете увеличить кумулятивную частоту любого элемента, увеличив значение числа, хранящегося в этом месте, а затем увеличивая частоты всего, что приходит потом. Например, чтобы увеличить кумулятивную частоту 3 на 7, мы могли бы добавить 7 к каждому элементу массива в позиции или после позиции 3, как показано здесь:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
Проблема заключается в том, что для этого требуется время O (n), что довольно медленно, если n велико.
Один из способов, которым мы можем думать об улучшении этой операции, - это изменить то, что мы храним в ведрах. Вместо того, чтобы хранить кумулятивную частоту вплоть до данной точки, вы можете вместо этого думать о том, чтобы просто сохранить сумму, увеличиваемую текущей частотой по сравнению с предыдущим ведром. Например, в нашем случае мы перепишем вышеуказанные ведра следующим образом:
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
Теперь мы можем увеличить частоту внутри ведра за время O (1), просто добавив соответствующее количество к этому ведру. Однако общая стоимость выполнения поиска теперь становится O (n), так как мы должны пересчитать общее количество в ковше, суммируя значения во всех меньших ковших.
Первое важное понимание, которое нам нужно получить отсюда к двоичному индексированному дереву, заключается в следующем: вместо того, чтобы постоянно пересчитывать сумму элементов массива, предшествующих определенному элементу, что, если бы мы должны были прекомпопировать общую сумму всех элементов до определенных точек в последовательности? Если бы мы могли это сделать, тогда мы могли бы вычислить суммарную сумму в точке, просто суммируя правильную комбинацию этих заранее вычисленных сумм.
Один из способов сделать это - изменить представление из массива ведер в бинарное дерево узлов. Каждый node будет аннотирован со значением, которое представляет собой суммарную сумму всех узлов слева от заданного node. Например, предположим, что мы построим следующее двоичное дерево из этих узлов:
4
/ \
2 6
/ \ / \
1 3 5 7
Теперь мы можем увеличить каждый node, сохранив кумулятивную сумму всех значений, включая node и его левое поддерево. Например, учитывая наши значения, мы сохраним следующее:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
Учитывая эту древовидную структуру, легко определить кумулятивную сумму до точки. Идея такова: мы поддерживаем счетчик, первоначально 0, затем выполняем обычный бинарный поиск до тех пор, пока не найдем node. По мере этого мы также имеем следующее: в любое время, когда мы двигаемся вправо, мы также добавляем текущее значение в счетчик.
Например, предположим, что мы хотим найти сумму для 3. Для этого мы делаем следующее:
Вы могли бы предположить, что и этот процесс выполняется в обратном порядке: начиная с заданного node, инициализируйте счетчик значением node, затем поднимите дерево к корню. Каждый раз, когда вы будете следовать правильной дочерней ссылке вверх, добавьте значение в node, к которому вы приходите. Например, чтобы найти частоту для 3, мы могли бы сделать следующее:
Чтобы увеличить частоту node (и, неявно, частоты всех узлов, которые появляются после нее), нам нужно обновить набор узлов в дереве, которые включают в себя node в его левом поддереве. Для этого мы делаем следующее: увеличиваем частоту для этого node, а затем начинаем идти к корню дерева. Каждый раз, когда вы следуете ссылке, которая поднимает вас как левый ребенок, увеличьте частоту node, с которой вы сталкиваетесь, добавив текущее значение.
Например, чтобы увеличить частоту node 1 на пять, мы сделаем следующее:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
Начиная с node 1, увеличьте его частоту на 5, чтобы получить
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
Теперь перейдите к его родительскому объекту:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Мы следили за левой дочерней ссылкой вверх, поэтому мы также увеличиваем эту частоту node:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Теперь перейдем к его родительскому объекту:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Это была ссылка с дочерним потомком, поэтому мы также увеличиваем этот node:
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
И теперь мы закончили!
Последний шаг состоит в том, чтобы преобразовать его в двоичное индексированное дерево, и именно здесь мы можем делать забавные вещи с двоичными числами. Позвольте переписать каждый индекс ведра в это дерево в двоичном формате:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
Здесь мы можем сделать очень, очень классное наблюдение. Возьмите любое из этих двоичных чисел и найдите самое последнее 1, которое было установлено в номере, затем отбросьте этот бит вместе со всеми битами, которые появляются после него. Теперь у вас осталось следующее:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
Вот действительно, действительно классное наблюдение: если вы считаете, что 0 означает "левый", а "1" означает "правильно", остальные бит на каждом номере указывают точно, как начать с корня, а затем перейти к этому номер. Например, node 5 имеет двоичный шаблон 101. Последний 1 является окончательным битом, поэтому мы отбрасываем его, чтобы получить 10. Действительно, если вы начинаете с корня, идите вправо (1), затем идите влево (0), вы попадаете в node 5!
Причина, по которой это важно, заключается в том, что наши операции поиска и обновления зависят от пути доступа из node к корневому каталогу и соответствуют ли мы левым или правым дочерним ссылкам. Например, во время поиска мы просто заботимся о левых ссылках, которые мы следуем. Во время обновления мы просто заботимся о правильных ссылках, которые мы придерживаемся. Это двоичное индексированное дерево делает все это супер эффективно, просто используя бит в индексе.
Ключевым трюком является следующее свойство этого идеального двоичного дерева:
Учитывая node n, следующий node на пути доступа к корню, в котором мы идем вправо, задается путем двоичного представления n и удаления последнего 1.
Например, посмотрите путь доступа для node 7, который равен 111. Узлы на пути доступа к корню, который мы используем, которые связаны с правильным указателем вверх, составляют
Все это правильные ссылки. Если мы возьмем путь доступа для node 3, который равен 011, и посмотрим на узлы, где мы идем правильно, получим
Это означает, что мы можем очень, очень эффективно вычислить суммарную сумму до node следующим образом:
Аналогично, подумайте о том, как мы будем делать шаг обновления. Чтобы сделать это, мы хотели бы следовать пути доступа к корню, обновляя все узлы, где мы следовали по левой ссылке вверх. Мы можем сделать это, выполнив вышеуказанный алгоритм, но переключая все 1 на 0 и 0 на 1.
Последний шаг в двоичном индексированном дереве состоит в том, чтобы отметить, что из-за этой побитовой обманки нам даже не нужно явно хранить дерево. Мы можем просто сохранить все узлы в массиве длины n, а затем использовать методы побитового сгибания для неявной навигации по дереву. Фактически, именно то, что делает побитовое индексированное дерево - оно хранит узлы в массиве, затем использует эти побитовые трюки, чтобы эффективно имитировать ходьбу вверх в этом дереве.
Надеюсь, это поможет!