Главная

Рубрика «структуры данных» - 11

Персистентные деревья отрезков

2012-04-24 в 17:51, admin, рубрики: Алгоритмы, персистентные структуры данных, Программирование, структуры данных, метки: персистентные структуры данных, структуры данных

Введение

Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).

Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).

Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.
Читать полностью »

Структура Radix Tree для сжатия данных

2012-03-31 в 15:45, admin, рубрики: c++, radix tree, Алгоритмы, исходники, сжатие данных, структуры данных, метки: radix tree, Алгоритмы, исходники, сжатие данных, структуры данных

Структура Radix Tree для сжатия данных Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.
Читать полностью »

Алгоритмы / [Из песочницы] Sqrt-декомпозиция (корневая оптимизация)

2012-02-27 в 12:56, admin, рубрики: структуры данных, метки: структуры данных

Sqrt-декомпозиция — это метод, или структура данных, позволяющая в режиме онлайн проводить такие операции, как подсчет суммы на отрезке за и обновление элемента за . Существуют более эффективные структуры, такие как дерево фенвика или дерево отрезков, которые оба запроса обрабатывают за . Однако я хочу рассказать про корневую оптимизацию, т.к. в этом методе заложена идея, применимая к задачам другого типа.