Вейвлет деревья

Succinct data structures свежее веяние в алгоритмистике. В русскоязычной школе материала мало, нет даже устоявшегося перевода. Будем восполнять этот пробел. На правах первопроходцев терминологию будем вводить налету. Пусть, скажем, компактные структуры данных. На Хабре уже появилась хорошая ознакомительная статья.

Под катом развитие темы с описанием пары новых(такое вы не найдете у Кнута) трюков структур, примеры применения и реализация на языке Go.
 

Итак — вейвлет дерево

Поиск в Яндекс подскажет вам вейвлет преобразование, как альтернативу преобразованию Фурье в цифровой обработке сигнала с разложением на высоко и низкочастотные составляющие, что позволяет отбросить высокочастотную и осуществить сжатие с предсказуемыми потерями. Сегодня не об этом. Вейвлет деревья были предложены Grossi, Gupta, Vitter в 2003 как компактное представление последовательности на конечном алфавите с гарантированно быстрыми методами доступа.