Всем привет!

Недавно на хабрахабре была опубликована статья про такую структуру данных, как списки с пропусками. Как мне показалось, структура весьма интересна и при этом проста в использовании. Именно поэтому сейчас я решил поэкспериментировать со структурой на различных задачах и попробовать реализовать над ней различные модификации. "Базовые" операции достаточно хорошо описаны в статье с хабрахабра, а также в статье с вики-конспектов ИТМО. Поэтому я не буду на них останавливаться и сразу перейду к более интересным.

Базовая реализация.

Здесь "чистый" вариант списков с пропусками — реализованы самые базовые операции — поиск, вставка, удаление.

Код

Добавляем работу с порядковыми статистиками.

Теперь нам понадобятся функции find_by_order() и order_of_key(). Для того, чтобы использовать их в сбалансированных деревьях, мы поддерживали размеры поддеревьев. Здесь же прийдётся дополнительно поддерживать длины ссылок. После этого обе функции реализуются очень легко. Для первой мы заменяем в условии проверку значений на проверку текущей длины от начала, то есть, на проверку порядкового номера. Во второй же функции мы делаем всё аналогично обычному find(), но при этом записываем в отдельную переменную длину пройденного пути.

Код

Делаем структуру по неявному ключу.

Фактически, добавив операцию find_by_order() из предыдущего пункта мы уже получили все возможности для того, чтобы производить операции по неявному ключу. Всё, что нужно для этого — вместо функции find() при вставке использовать функцию find_by_order(). Для удобства можно перегрузить оператор [].

Код

Вообще, я ещё планировал написать rope (возможность вырезать/вставлять отрезки) и, может быть, модификации на подотрезках, но после того, как структура не справилась с довольно простыми задачами по лимиту времени, моё рвение поуменьшилось :) В любом случае опубликую то, что уже было сделано, может, кому-то ещё будет интересно или полезно.

P.S. А что вы думаете об этой структуре? Есть ли среди посетителей codeforces те, кто ей пользуется? Насколько разумно использовать списки с пропусками на контестах? Какие ещё могут быть сделаны полезные модификации структуры? И да, моя реализация необычайно медленна и местами вмещает слишком много кода. Может, кто-нибудь знает варианты получше?