DS Структуры данных Структура данных
Дерево Фенвика
Также: Fenwick tree · binary indexed tree · BIT · двоичное индексированное дерево · дерево Рябко · кумулятивные частоты · lowbit
Сумма первых i элементов и изменение одного элемента — оба за O(log n), в массиве той же длины, что данные, и циклом в три строки. Ячейка с номером i хранит сумму блока длиной в младшую единицу двоичной записи i. Структуру придумали для арифметического кодирования: на «Войне и мире», сжатой по словам, видно, зачем.
Арифметический код сжимает текст тем сильнее, чем точнее угадывает следующее слово. Модель ведёт счётчик для каждого слова словаря, и на каждом шаге кодеру нужно знать две вещи: сколько «весят» все слова, которые стоят в таблице раньше текущего, и сколько весит оно само. Потом счётчик слова растёт на единицу, и следующее слово кодируется уже по новой таблице. В словаре «Войны и мира» 47 585 слов: сумма до слова в середине алфавита — это двадцать с лишним тысяч сложений, и так 436 тысяч раз. Нажмите «Пуск».
На первых ста тысячах слов кодер тратит в среднем 12,05 бита на слово — 147,1 КБ. Номер слова, записанный целиком, занимает 15,54 бита: модель экономит почти четверть, потому что частые слова получают широкие отрезки и короткий код. А теперь счётчики под полосой. Чтобы сложить веса всех слов до текущего, простой проход по таблице делает в среднем 21 826 сложений. Дерево Фенвика делает 15,7 шага на слово — и на сумму, и на прибавление единицы вместе. Переключите на «Буквами»: в алфавите 33 буквы и пробел, проход стоит 15 сложений, и никакое дерево не нужно. Буквами, кстати, выходит 27 бит на слово, вдвое с лишним больше, — правда, модели слов словарь достался даром.
Идея
Ячейка с номером i хранит сумму блока элементов, который кончается на i и имеет длину i & −i — младшую единицу двоичной записи i. Сумма первых i элементов — это ячейка i, потом ячейка i без младшей единицы, и так до нуля: блоки ложатся встык справа налево. Прибавить к элементу s — значит обновить все ячейки, чьи блоки его содержат: s, s + младшая единица, и так дальше. Оба пути не длиннее числа двоичных разрядов в n.
Блоки получаются такие. У нечётных номеров младшая единица — сама единица: ячейки 1, 3, 5, 7 хранят по одному элементу. Ячейки 2, 6, 10, 14 — пары, 4 и 12 — четвёрки, 8 — восьмёрку, 16 — все шестнадцать. Нумерация с единицы: у нуля младшей единицы нет. Ниже шестнадцать ячеек над длинами слов романа: в столбце k — слова из k букв, в последнем — из шестнадцати и длиннее.
Нажмите на столбец 13. В двоичной записи 13 — это 1101. Ячейка 13 хранит один столбец, ячейка 12 = 1100 — столбцы 9–12, ячейка 8 = 1000 — столбцы 1–8. Вместе это ровно столбцы 1–13, и сумма собрана из трёх чисел. Теперь добавляйте слова кнопкой «+1 слово»: если в слове четыре буквы, единица уйдёт в ячейки 4 = 00100, 8 = 01000 и 16 = 10000 — во все блоки, которые содержат столбец 4. Путь суммы снимает младшую единицу, путь изменения её прибавляет. Это и есть вся структура; операция i & −i разобрана в статье о битовых трюках.
Дерево здесь не нарисовано, но оно есть: родитель ячейки i на пути изменения — ячейка i + младшая единица, и её блок начинается там же или левее, а кончается правее. Отсюда и название binary indexed tree, «дерево, проиндексированное двоичными числами». Указателей нет, лишних ячеек нет: массив той же длины, что данные.
Почему путей хватает log n шагов
Пусть ячейка i хранит сумму элементов с номерами от i − lowbit(i) + 1 до i. Тогда: (1) блоки ячеек i, i − lowbit(i), … до нуля покрывают элементы 1…i без пропусков и наложений, и их не больше ⌊log₂ i⌋ + 1; (2) элемент s лежит в блоках ячеек s, s + lowbit(s), … и ни в каких других, и этих ячеек не больше ⌊log₂ n⌋ + 1.
(1) Блок ячейки j кончается на j, а начинается сразу после j − lowbit(j) — номера следующей ячейки пути. Поэтому соседние блоки стыкуются. Каждый шаг снимает одну единичку двоичной записи, а их в i не больше ⌊log₂ i⌋ + 1.
(2) Пусть j > s и блок j содержит s: j − lowbit(j) < s ≤ j. Обозначим 2k = lowbit(j). Тогда j и s совпадают во всех битах старше k-го: j − 2k — это j с обнулённым битом k, и s лежит между ним и j. Значит, s совпадает с j выше бита k, в бите k у s ноль, а ниже есть единицы. Обратно: j получается из s так — взять нулевой бит s, под которым есть единицы, поставить его в единицу, а всё ниже обнулить. Путь «прибавить младшую единицу» перебирает ровно такие биты снизу вверх: прибавление стирает младший хвост единиц и ставит единицу в первый ноль над ним. Например, 5 = 101 → 110 → 1000 → 10000. С каждым шагом младшая единица номера растёт хотя бы вдвое, поэтому шагов не больше ⌊log₂ n⌋ + 1.
На сумму уходит столько шагов, сколько единиц в двоичной записи номера, на изменение — не больше, чем нулей выше младшей единицы, и ещё один. В кодере словаря номера 16-битные, и на сумму с прибавлением вместе уходит 15,7 шага на слово.
Построить дерево можно за O(n), а не за n изменений: каждая ячейка, когда её сумма готова, прибавляет её к ячейке i + lowbit(i) — своему родителю. Если все счётчики равны единице, как в начале работы кодера, ячейка i хранит ровно lowbit(i).
Чья это сумма
Декодеру нужен обратный вопрос. Он знает точку на полосе — число от нуля до общей суммы — и должен найти слово, чей отрезок её накрывает: наименьшее s, у которого сумма первых s + 1 счётчиков больше точки. Можно двоично искать по префиксным суммам, но это O(log² n). Дерево Фенвика позволяет спуститься за O(log n): идём по степеням двойки сверху вниз и пробуем шагнуть на 2k вперёд. Ячейка, в которую мы попадаем, хранит ровно блок между старой позицией и новой — потому что новая позиция кратна 2k, а старая кратна 2k+1. Если блок целиком меньше остатка точки, шагаем и вычитаем его; иначе оставляем позицию и пробуем шаг вдвое короче.
Нажмите на полосу в первой сцене: спуск проверит 17 степеней двойки и найдёт слово. Декодер из листинга ниже так восстанавливает все 100 000 слов по одним только началам отрезков, тратя 25,2 шага на слово — спуск и прибавление единицы. Тем же спуском находится k-я порядковая статистика: кнопка «Медиана длины» во второй сцене ищет слово, которое стоит посередине, если все слова выстроить по длине.
Счётчики для арифметического кода
В 1987 году Ян Виттен, Рэдфорд Нил и Джон Клири опубликовали в Communications of the ACM подробную реализацию арифметического кодирования на C. Их адаптивная модель держит счётчики 257 символов — байтов и конца файла — вместе с накопленными суммами, и авторы прямо пишут, что обновлять модель дорого: суммы нужно поддерживать после каждого символа. Чтобы проход был короче, они держат таблицу упорядоченной по частоте, как самоорганизующийся список: частые символы оказываются в начале. Для байтов этого хватает. Для слов — нет: даже если бы таблица «Войны и мира» была заранее упорядочена по частоте, проход до слова стоил бы в среднем 4098 сложений.
В 1989 году Борис Рябко описал ту же структуру — суммы блоками по степеням двойки — в статье о быстром адаптивном коде. В 1994 году Питер Фенвик опубликовал её в журнале Software: Practice and Experience в статье «Новая структура данных для таблиц накопленных частот», назвал binary indexed tree, и под его именем она разошлась по учебникам и олимпиадам. Повод у обоих был один и тот же — арифметическое кодирование с меняющимися частотами.
Код
Кодер и декодер «Войны и мира» по словам. Модель знает словарь романа заранее — передавать его кодер не стал бы бесплатно, — а частоты узнаёт по ходу текста. Вместо самого арифметического кода программа считает его идеальную длину: log₂(общая сумма / счётчик слова) бит на слово. Арифметический код с точной арифметикой длиннее этой суммы не больше чем на два бита на весь текст, реальные кодеры с конечной точностью теряют ещё немного. Кодер запоминает начало отрезка каждого слова, декодер по этим числам спуском восстанавливает текст.
first 100000 words: 12.049 bits per word, 147.1 KB steps per word: tree 15.7, plain table 21826 decoded back: every word matches; first words: лев толстой том первый часть первая
Длину кода для всего романа программа считает без дерева: она зависит только от счётчиков, а не от того, где слово стоит в таблице, — 11,692 бита на слово, 622,4 КБ. Дерево нужно, чтобы выдать сам код: начало отрезка каждого слова.
Дерево Фенвика естественно обобщается на две координаты: ячейка (i, j) хранит сумму прямоугольного блока, и пути по двум координатам вкладываются один в другой. Ниже все 19 073 землетрясения силой от пяти с 2015 по 2025 год идут на сетку по градусу: после каждого года программа спрашивает, сколько их случилось к этому моменту в трёх прямоугольниках карты. Каждое событие — 18,8 шага, каждый прямоугольник — четыре суммы от угла, 50,7 шага, а клеток на сетке 64 800.
Сколько это стоит
| Операция | Время | Почему |
|---|---|---|
| построить | O(n) | каждая ячейка отдаёт сумму родителю |
| сумма первых i | O(log n) | столько шагов, сколько единиц в i |
| сумма отрезка [l, r] | O(log n) | разность двух сумм префиксов |
| изменить элемент | O(log n) | младшая единица номера растёт с каждым шагом |
| спуск: чья это сумма, k-й элемент | O(log n) | по шагу на степень двойки |
| двумерные: точка и прямоугольник | O(log n · log m) | путь по второй координате на каждом шаге первой |
Память — n + 1 чисел, ровно столько, сколько данных. Замер — тот самый шаг кодера, сумма до символа и прибавление единицы, на алфавитах от 16 до полумиллиона символов: простая таблица, дерево Фенвика и дерево отрезков снизу вверх, которое умеет то же самое.
На шестнадцати символах простая таблица на Python быстрее дерева: срез складывается на C. На 128 они наравне, а на полумиллионе символов таблица медленнее в 540 раз на Python и в 1440 раз на Go. Дерево отрезков в этой гонке медленнее Фенвика в 1,6–2 раза на Python и в 1,7–3 раза на Go: путь Фенвика — одна переменная и одна битовая операция на шаг, а дерево отрезков собирает сумму с двух концов и хранит вдвое больше ячеек.
Что ему не по силам
Сумма отрезка — это разность двух префиксов, и так работает любая операция, у которой есть обратная: сложение, исключающее «или», умножение по модулю простого числа. Минимум на произвольном отрезке так не получить: минимум префикса дерево Фенвика хранит, а «вычесть» минимум нельзя. Нужен минимум на отрезке — берите дерево отрезков или, если данные не меняются, разреженную таблицу.
Зато с отрезками можно схитрить через разности, как в разностном массиве. Если хранить в дереве разности соседних элементов, прибавка к отрезку [l, r] — это два изменения, в l и в r + 1, а значение элемента — сумма префикса. Два таких дерева вместе дают и прибавку к отрезку, и сумму отрезка. Присвоение отрезку значения так не выражается: для него нужны отложенные операции дерева отрезков.
Ещё один частый приём — счётчики по значениям. Если в дереве на месте v лежит число уже встреченных элементов со значением v, то сумма префикса отвечает, сколько из них меньше нового, — это ранг нового элемента и число инверсий, которые он создаёт. Значения до миллиарда сначала сжимают до номеров. Так же, с максимумом вместо суммы, работает быстрый вариант наибольшей возрастающей подпоследовательности: максимум на префиксе обратной операции не требует.
Задачи
В первой задаче каждое новое землетрясение из каталога USGS нужно поставить на место среди всех прежних: счётчики по сжатым значениям. Во второй нужно написать декодер адаптивного кода и восстановить начало «Войны и мира» по началам отрезков — спуск по дереву.
Место в каталоге ДекодерДанные: «Война и мир», Л. Н. Толстой, общественное достояние Землетрясения: каталог USGS, общественное достояние