Описание тега binary-indexed-tree

Описание тега Вопросы с тегом

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

Двоичное индексированное дерево(BIT), также известное как дерево Фенвика, представляет собой структуру данных, обеспечивающую эффективные методы для расчета и управленияprefix sumsтаблицы значений. Его предложил Питер Фенвик в 1994 году.

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

Первоначальное строительство BIT требует O(nLogn)время. Но он может эффективно запускать запрос диапазона на построенном дереве вO(logn) время, а также обновить дерево в O(logn)время. Самое главное, BIT может хранить таблицу частот или дерево сборки вO(n) пространство памяти.

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

Ссылка