Структуры данных

Fenwick Tree (BIT): Префиксные суммы за O(log n)

Цели урока

  • Понять проблему: быстрые sum + update
  • Освоить идею: ответственность за диапазоны через биты
  • Реализовать query и update за O(log n)
  • Применить для подсчёта инверсий

Предварительные знания

  • Массивы
  • Битовые операции
  • Массивы

Миллион транзакций, и нужно постоянно отвечать 'сколько потрачено за период X-Y?' При этом новые транзакции добавляются каждую секунду. Пересчитывать всё - слишком долго. Fenwick Tree делает это за микросекунды.

  • Финансовые системы - агрегация транзакций в реальном времени
  • Competitive programming - классика олимпиадных задач
  • Git - подсчёт изменений в диапазонах коммитов
  • Базы данных - индексы для range queries

Питер Фенвик и Binary Indexed Tree

Питер Фенвик, информатик из Оклендского университета, представил структуру в статье 1994 года под названием «A New Data Structure for Cumulative Frequency Tables». Он занимался сжатием данных, где арифметическим кодировщикам нужно хранить и запрашивать кумулятивные частоты, меняющиеся по мере кодирования символов. Существующие подходы заставляли выбирать между быстрыми запросами и быстрыми обновлениями. Идея Фенвика состояла в том, чтобы двоичное представление индекса определяло, за какой диапазон массива этот индекс отвечает, используя трюк lowbit x & (-x) для перехода между диапазонами. Это дало и запрос префиксной суммы, и точечное обновление за O(log n) с очень небольшим кодом и памятью. Сегодня структуру широко знают как Binary Indexed Tree, или BIT, и она остаётся базовым инструментом спортивного программирования.

Проблема: Сумма на отрезке с обновлениями

**Задача:** массив чисел. Нужно быстро отвечать на запросы суммы [l, r] и обновлять элементы.

**Дилемма:** либо быстрые запросы, либо быстрые обновления. А можно оба за O(log n)?

**Fenwick Tree (Binary Indexed Tree):** обе операции за O(log n)!

Fenwick Tree решает проблему:

Идея: Ответственность за диапазоны

**Главное наблюдение:** каждый индекс i отвечает за сумму определённого диапазона элементов.

Количество элементов = **младший установленный бит** индекса!

BIT[4] (4 = 100 в двоичном) отвечает за:

Lowbit: Битовый трюк

**lowbit(x)** - значение младшего установленного бита.

**Почему работает?** В дополнительном коде -x = ~x + 1. При инвертировании и добавлении 1 все биты правее младшего меняются, а сам младший бит остаётся.

lowbit(10) = ? (10 = 1010 в двоичном)

Query: Сумма prefix[1..i]

**Запрос суммы:** идём от i к 1, вычитая lowbit на каждом шаге.

**Сложность:** O(log n) - на каждом шаге убираем минимум один бит.

Сколько шагов в query(15)?

Update: Обновление элемента

**Обновление:** идём от i к n, прибавляя lowbit на каждом шаге.

**Симметрия:** query идёт вниз (-lowbit), update идёт вверх (+lowbit).

При update(5, delta) какие BIT обновятся (n=8)?

Полная реализация

range_query(l, r) вычисляется как:

Применения Fenwick Tree

  • **Подсчёт инверсий** - сколько пар (i,j) где i<j, но a[i]>a[j]
  • **Range updates** - прибавить delta ко всем элементам [l..r]
  • **2D Fenwick Tree** - суммы на прямоугольниках в матрице
  • **Порядковая статистика** - k-ый элемент в динамическом множестве

Fenwick Tree - компактнее Segment Tree (в 2 раза меньше памяти) и быстрее на практике благодаря лучшей cache locality.

Fenwick Tree заменяет Segment Tree во всех задачах на отрезках

Fenwick Tree проще и быстрее для prefix sum и point update. Segment Tree мощнее: поддерживает range update, range max/min, произвольные ассоциативные операции. Fenwick не поддерживает range max/min

Обе структуры работают за O(log n), но Segment Tree более универсальна. Fenwick выигрывает по константе и памяти только для суммы

Fenwick Tree vs Segment Tree:

Fenwick Tree (BIT)

  • Решает: prefix sum + point update за O(log n)
  • lowbit(x) = x & (-x) - младший установленный бит
  • query: идём вниз, вычитая lowbit
  • update: идём вверх, прибавляя lowbit
  • Компактнее и быстрее Segment Tree для простых операций

Вопросы для размышления

  • Fenwick Tree поддерживает prefix sum за O(log n). Как с его помощью ответить на запрос суммы произвольного диапазона [l, r]?

Связанные структуры

Fenwick Tree - частный случай более общего Segment Tree. Для сложных операций (min/max на отрезке с обновлениями) нужен Segment Tree.

  • Segment Tree — Более универсальная структура для запросов на отрезках

Связанные уроки

  • ds-01-arrays — Структура неявно хранится внутри плоского массива
  • ds-19-segment-tree — Дерево отрезков решает те же запросы диапазона более общо
  • alg-36-prefix-sum — Добавляет обновляемые префиксные суммы к статической идее
  • alg-35-bit-manipulation — Навигация по индексам опирается на трюки с младшим битом
  • db-09-indexes-btree — Индексы БД так же ускоряют агрегатные запросы по диапазону
Fenwick Tree (BIT): Префиксные суммы за O(log n)

0

1

Войти