Битовое дерево¶

Битовое дерево (англ. bit tree, Fenwick tree, Binary Indexed Tree, BIT) — это структура данных, предназначенная для эффективного вычисления значений префиксных функций (например, суммы, минимума, максимума, произведения) на массиве, а также для выполнения точечных обновлений (изменения одного элемента). Относится к классу деревьев отрезков, но отличается существенно меньшим расходом памяти (требует ровно n ячеек, где n — размер исходного массива) и простотой реализации. Впервые описана Райаном Фенвиком в 1994 году.

¶История

Идея, лежащая в основе битового дерева, была предложена новозеландским учёным Райаном Фенвиком в 1994 году в статье «A New Data Structure for Cumulative Frequency Tables» (опубликована в журнале Software: Practice and Experience). Фенвик искал способ быстро вычислять кумулятивные частоты в статистических таблицах, не прибегая к полному пересчёту массива при каждом изменении. Предложенная им структура позволяла выполнять обе операции (запрос префикса и точечное обновление) за логарифмическое время O(log n), используя при этом лишь n элементов памяти. С тех пор битовое дерево стало стандартным инструментом в олимпиадном программировании, алгоритмических задачах и приложениях, связанных с обработкой последовательностей.

¶Принцип работы

Битовое дерево строится на основе исходного массива A[1..n] (индексация обычно начинается с единицы). Вспомогательный массив T[1..n] (само дерево) хранит суммы (или другие агрегаты) не отдельных элементов, а диапазонов, длина которых определяется двоичным представлением индекса. Ключевая операция — выделение младшего единичного бита индекса (Least Significant Bit, LSB), которая выполняется с помощью побитовой операции: i & -i. Значение LSB для индекса i равно степени двойки, на которую делится i.

¶Построение

Изначально массив T заполняется нулями. Затем для каждого элемента A[i] выполняется операция обновления (см. ниже). В результате T[i] хранит агрегат для диапазона [i - LSB(i) + 1, i].

¶Запрос префикса (суммы)

Для вычисления суммы элементов от 1 до k (префиксная сумма) используется следующий алгоритм:

1. Установить результат = 0.
2. Пока k > 0:

• Прибавить T[k] к результату.
• Вычесть из k значение LSB(k): k = k - (k & -k).

1. Вернуть результат.

Пример: для k = 6 (двоичное 110) LSB(6) = 2. Сумма будет: T[6] + T[4] (так как 6 - 2 = 4, LSB(4) = 4, 4 - 4 = 0). T[6] хранит сумму A[5]+A[6], T[4] — сумму A[1]+A[2]+A[3]+A[4].

¶Точечное обновление

Для изменения значения элемента A[pos] на величину delta (прибавление) выполняется:

1. Пока pos ≤ n:

• Прибавить delta к T[pos].
• Прибавить к pos значение LSB(pos): pos = pos + (pos & -pos).

Пример: обновление элемента A[3] (delta = +5). LSB(3) = 1. T[3] += 5; pos = 4; LSB(4) = 4; T[4] += 5; pos = 8; и так далее, пока pos ≤ n.

¶Сложность

Обе основные операции (запрос префикса и точечное обновление) выполняются за O(log n). Построение дерева из массива — O(n log n) при последовательном обновлении, но может быть выполнено за O(n) с помощью специальной процедуры (например, заполнение T[i] = A[i], затем для каждого i прибавить T[i] к T[i + LSB(i)]).

¶Классификация и разновидности

¶По типу агрегируемой функции

• Суммарное дерево (Fenwick Sum Tree) — самый распространённый вариант. Позволяет вычислять сумму на отрезке [l, r] как sum(r) - sum(l-1).
• Дерево для минимума/максимума — требует модификации, так как операция вычитания не применима. Для запроса минимума на отрезке используется битовое дерево с поддержкой обновления и запроса префикса, но для произвольного отрезка необходимо дополнительное дерево или иная структура (например, дерево отрезков).
• Дерево для XOR — работает аналогично суммарному, так как XOR обратим.

¶По направлению

• Прямое дерево — стандартное, описанное выше. Обрабатывает запросы префиксов от 1 до k.
• Обратное дерево — строится для запросов суффиксов (от k до n). Реализуется заменой операций: при обновлении индекс уменьшается, при запросе — увеличивается.

¶Многомерные битовые деревья

Обобщение на многомерные массивы (например, двумерное битовое дерево). Позволяет выполнять запросы суммы в прямоугольной области и точечные обновления за O(log n × log m). Используется в задачах обработки изображений, геоинформационных системах (ГИС) и анализе данных.

¶Применение

¶Вычислительная математика и статистика

• Кумулятивные частоты — исходная задача Фенвика. Используется в статистических пакетах для быстрого построения гистограмм и вычисления процентилей.
• Динамические массивы — поддержка суммы на отрезке при частых изменениях элементов.

¶Олимпиадное программирование

Битовое дерево — одна из базовых структур данных, обязательных для изучения в рамках подготовки к соревнованиям (например, ACM ICPC, Всероссийская олимпиада школьников по информатике). Применяется в задачах на:

• Подсчёт инверсий в массиве (с использованием сжатия координат).
• Динамические запросы на отрезке (сумма, количество элементов, удовлетворяющих условию).
• Задачи на интервалы (например, «Звёзды» — классическая задача с двумерным битовым деревом).

¶Информационные системы

• Базы данных — для ускорения агрегатных запросов (SUM, COUNT) по временным рядам или индексам.
• Графические редакторы — для быстрого вычисления гистограмм яркости пикселей.

¶Криптография и кодирование

• Коды Грея — битовые деревья используются при построении некоторых алгоритмов коррекции ошибок.

¶Пример реализации (псевдокод)

``` class BIT: n: int tree: array of int

function init(size): n = size tree = array of size n+1 filled with 0

function add(pos, delta): while pos <= n: tree[pos] += delta pos += pos & -pos

function sum(pos): result = 0 while pos > 0: result += tree[pos] pos -= pos & -pos return result

function range_sum(l, r): return sum(r) - sum(l-1) ```

¶Преимущества и недостатки

¶Преимущества

• Экономия памяти — ровно n элементов (против 4n для дерева отрезков).
• Простота реализации — код занимает несколько строк.
• Высокая скорость — константа в O(log n) меньше, чем у дерева отрезков, за счёт отсутствия рекурсии и простых арифметических операций.
• Лёгкость обобщения на многомерные случаи.

¶Недостатки

• Ограниченность операций — битовое дерево эффективно только для обратимых агрегатов (сумма, XOR, произведение). Для минимума/максимума на произвольном отрезке требуется модификация или дополнительная структура.
• Сложность с обновлением диапазона — стандартное битовое дерево не поддерживает массовые обновления (изменение всех элементов на отрезке). Для этого требуется два дерева (техника разностных массивов) или дерево отрезков.
• Необходимость сжатия координат — при работе с большими разреженными данными (например, координаты точек) требуется предварительное сжатие, что увеличивает время подготовки.

¶Интересные факты

• Название «битовое дерево» связано с тем, что операции основаны на двоичном представлении индексов.
• В русскоязычной литературе часто встречается название «дерево Фенвика» (по имени автора).
• Битовое дерево может быть использовано для реализации «дерева отрезков» с ограниченным функционалом, но с меньшим расходом памяти.
• Существует вариант битового дерева с поддержкой обновления диапазона и запроса диапазона (Range Update — Range Query, RURQ), который использует два дерева.

¶Источники

• Fenwick, P. M. (1994). «A New Data Structure for Cumulative Frequency Tables». Software: Practice and Experience, 24(3), 327–336.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). «Алгоритмы: построение и анализ» (3-е изд.). — Глава 14: «Деревья Фенвика».
• Окулов, С. М. (2010). «Программирование в алгоритмах». — Раздел 2.4: «Дерево Фенвика».
• Материалы сообщества олимпиадного программирования Codeforces (раздел «Fenwick Tree»).