Бинарное индексированное дерево не имеет или почти не имеет литературы по сравнению с другими структурами данных. Единственное место, где это преподается, это учебник по topcoder . Хотя учебник завершен во всех объяснениях, я не могу понять интуицию за таким деревом? Как это было изобретено? Что является фактическим доказательством его правильности?
algorithms
binary-trees
trees
Nikunj Banka
источник
источник
Ответы:
Интуитивно вы можете представить двоичное индексированное дерево как сжатое представление двоичного дерева, которое само по себе является оптимизацией стандартного представления массива. Этот ответ входит в один из возможных выводов.
Предположим, например, что вы хотите хранить кумулятивные частоты в общей сложности для 7 различных элементов. Вы можете начать с написания семи блоков, в которые будут распределяться числа:
Теперь предположим, что кумулятивные частоты выглядят примерно так:
Используя эту версию массива, вы можете увеличивать совокупную частоту любого элемента, увеличивая значение числа, хранящегося в этом месте, а затем увеличивая частоты всего, что будет потом. Например, чтобы увеличить совокупную частоту 3 на 7, мы могли бы добавить 7 к каждому элементу в массиве в позиции 3 или после нее, как показано здесь:
Проблема в том, что для этого требуется время O (n), что довольно медленно, если n велико.
Один из способов улучшить эту операцию - изменить то, что мы храним в корзинах. Вместо того, чтобы сохранять накопленную частоту до заданной точки, вы можете вместо этого думать о том, чтобы просто сохранить величину, на которую текущая частота увеличилась по сравнению с предыдущим сегментом. Например, в нашем случае мы переписали бы вышеупомянутые сегменты следующим образом:
Теперь мы можем увеличить частоту внутри сегмента за время O (1), просто добавив соответствующую сумму в этот интервал. Тем не менее, общая стоимость выполнения поиска теперь становится O (n), так как мы должны пересчитать общее количество в сегменте, суммируя значения во всех меньших сегментах.
Первое важное понимание, которое нам нужно получить отсюда к бинарному индексируемому дереву, заключается в следующем: вместо того, чтобы непрерывно пересчитывать сумму элементов массива, которые предшествуют конкретному элементу, что, если бы мы должны были предварительно вычислить общую сумму всех элементов перед определенным точки в последовательности? Если бы мы могли сделать это, то мы могли бы вычислить кумулятивную сумму в точке, просто суммируя правильную комбинацию этих предварительно вычисленных сумм.
Один из способов сделать это - изменить представление с массива сегментов на двоичное дерево узлов. Каждый узел будет помечен значением, представляющим совокупную сумму всех узлов слева от данного узла. Например, предположим, что мы строим следующее двоичное дерево из этих узлов:
Теперь мы можем увеличить каждый узел, сохранив кумулятивную сумму всех значений, включая этот узел и его левое поддерево. Например, учитывая наши значения, мы будем хранить следующее:
Учитывая эту древовидную структуру, легко определить совокупную сумму с точностью до точки. Идея состоит в следующем: мы поддерживаем счетчик, изначально 0, затем выполняем обычный двоичный поиск до тех пор, пока не найдем рассматриваемый узел. При этом мы также делаем следующее: каждый раз, когда мы движемся вправо, мы также добавляем текущее значение к счетчику.
Например, предположим, что мы хотим найти сумму для 3. Для этого мы делаем следующее:
Вы могли бы также представить, что этот процесс выполняется в обратном порядке: начиная с данного узла, инициализируйте счетчик значением этого узла, затем поднимитесь по дереву к корню. Каждый раз, когда вы переходите по правой дочерней ссылке вверх, добавьте значение в узел, к которому вы пришли. Например, чтобы найти частоту для 3, мы могли бы сделать следующее:
Чтобы увеличить частоту узла (и, неявно, частоты всех узлов, следующих за ним), нам нужно обновить набор узлов в дереве, которые включают этот узел в свое левое поддерево. Чтобы сделать это, мы делаем следующее: увеличиваем частоту для этого узла, затем начинаем идти к корню дерева. Каждый раз, когда вы переходите по ссылке, которая превращает вас в левого ребенка, увеличивайте частоту встречаемого узла, добавляя текущее значение.
Например, чтобы увеличить частоту узла 1 на пять, мы бы сделали следующее:
Начиная с узла 1, увеличьте его частоту на 5, чтобы получить
Теперь перейдите к его родителю:
Мы пошли по левой дочерней ссылке вверх, поэтому мы также увеличиваем частоту этого узла:
Теперь перейдем к его родителю:
Это была левая дочерняя ссылка, поэтому мы также увеличиваем этот узел:
И теперь мы закончили!
Последний шаг - преобразовать это дерево в двоичное индексированное дерево, и именно здесь мы можем делать забавные вещи с двоичными числами. Давайте перепишем каждый индекс сегмента в этом дереве в двоичном виде:
Здесь мы можем сделать очень, очень крутое наблюдение. Возьмите любое из этих двоичных чисел и найдите самый последний 1, который был установлен в числе, затем отбросьте этот бит вместе со всеми битами, которые идут после него. Теперь у вас осталось следующее:
Вот очень, очень классное наблюдение: если вы трактуете 0 как «левый», а 1 как «правый», оставшиеся биты на каждом числе объясняют, как именно начать с корня, а затем перейти к этому числу. Например, узел 5 имеет двоичный шаблон 101. Последний 1 является последним битом, поэтому мы отбрасываем его, чтобы получить 10. Действительно, если вы начинаете с корня, идите направо (1), затем идите налево (0), вы заканчиваете на узле 5!
Это важно потому, что наши операции поиска и обновления зависят от пути доступа от узла до корня и от того, следуем ли мы по левым или правым дочерним ссылкам. Например, во время поиска мы просто заботимся о правильных ссылках, по которым следуем. Во время обновления мы просто заботимся о левых ссылках, по которым следуем. Это двоичное индексированное дерево делает все это очень эффективно, просто используя биты в индексе.
Ключевой трюк заключается в следующем свойстве этого совершенного бинарного дерева:
Например, взгляните на путь доступа для узла 7, который равен 111. Узлы на пути доступа к корню, который мы выбираем, включают в себя следование по правому указателю вверх:
Все это правильные ссылки. Если мы возьмем путь доступа для узла 3, который равен 011, и посмотрим на узлы, куда мы идем направо, мы получим
Это означает, что мы можем очень, очень эффективно вычислить накопленную сумму до узла следующим образом:
Точно так же, давайте подумаем о том, как мы сделаем шаг обновления. Чтобы сделать это, мы хотели бы следовать по пути доступа обратно до корня, обновляя все узлы, где мы следовали по левой ссылке вверх. Мы можем сделать это, по сути, используя вышеупомянутый алгоритм, но переключая все 1 на 0 и 0 на 1.
Последний шаг в двоичном индексированном дереве состоит в том, чтобы отметить, что из-за этого побитового трюка нам даже не нужно больше сохранять дерево явно. Мы можем просто сохранить все узлы в массиве длины n, а затем использовать методы побитового тиддлинга для неявной навигации по дереву. Фактически, это именно то, что делает побитовое индексируемое дерево - оно сохраняет узлы в массиве, а затем использует эти побитовые трюки, чтобы эффективно имитировать движение вверх по этому дереву.
Надеюсь это поможет!
источник
Я думаю, что оригинальная статья Фенвика намного понятнее. Ответ выше @templatetypedef требует некоторых «очень крутых наблюдений» об индексации идеального бинарного дерева, которые меня смущают и волшебны.
Фенвик просто сказал, что диапазон ответственности каждого узла в дереве запросов будет соответствовать его последнему установленному биту:
Например, поскольку последний установленный бит
6==00110является «2-битным», он будет отвечать за диапазон из 2 узлов. Для12==01100это "4-битный", поэтому он будет отвечать за диапазон 4 узлов.Поэтому при запросе
F(12)==F(01100)мы удаляем биты один за другим, получаяF(9:12) + F(1:8). Это не является почти строгим доказательством, но я думаю, что это более очевидно, если просто поместить их на ось чисел, а не в идеальное двоичное дерево, каковы обязанности каждого узла и почему стоимость запроса равна числу установить биты.Если это все еще неясно, бумага очень рекомендуется.
источник