Дерево смещений: работаем с динамически изменяемыми сегментированными массивами

Расскажу про задачу, которую решал, и проблему, с которой столкнулся.

Есть большой список, например, история сообщений чата. Есть окно просмотра (viewport), в которое попадает лишь малая часть списка. Нужно рисовать только видимую часть — то, что попадает во viewport. Рисовать требуется часто, 30 раз в секунду, то есть нужно уметь быстро находить видимые элементы. Более того, сообщения могут редактироваться, а следовательно, менять свой размер и удаляться. Хуже того, есть анимация — сообщения плавно перемещаются по списку. Например, после удаления сообщения «хвост» плавно заполняет образовавшееся пространство. Другими словами, надо быть готовыми к тому, что геометрия списка меняется каждый кадр.

Опишу несколько «наивных» решений с использованием стандартных контейнеров. Объясню, почему они неэффективны. Представлю эффективное решение с помощью так называемого дерева смещений (не путать с деревом отрезков — это другая структура данных).

Будет интересно тем, кто интересуется алгоритмами визуализации больших списков данных. Покажу реализацию дерева смещений на C++, как с помощью шаблонов сделать реализацию универсальной и настраиваемой.