Существует структура данных, называемая treap: это рандомизированное дерево двоичного поиска, которое также является кучей случайного генерирования так называемых "приоритетов".
Существует вариация этой структуры, где ключи неявные, они не хранятся в дереве, но мы рассматриваем упорядоченный индекс node в дереве как этот node. Нам нужно сохранить размер поддерева в каждом node вместо ключа. Этот метод позволяет нам думать о treap как о каком-то массиве, который поддерживает много операций в O (log N): вставка, удаление, реверсия подмассива, изменение интервала и т.д.
Я немного разбираюсь в этой структуре, но не так много. Я попытался это сделать, но я нашел только много статей о treap, но ничего об этом "скрытом treap" / "индексированном списке". Я даже не знаю его имени, потому что мой родной язык не английский и лекция, которую я слушал, использовал родной термин структуры, а не английский оригинальный термин. Этот родной термин может быть непосредственно переведен на английский язык как "Treap на неявных ключах" или "Декартово дерево на неявных ключах".
Может ли кто-нибудь указать мне на статью об этой структуре или сказать мне свое первоначальное имя? Спасибо.
P.S. Извините, если мой английский был недостаточно понятен.
UPD: Некоторое дополнительное объяснение структуры, которую я ищу.
Рассмотрим обычный treap со случайно выбранными приоритетами и ключами, которые являются фактическими пользовательскими данными, хранящимися в дереве. Тогда представьте, что у нас есть какая-то другая информация о пользователе, хранящаяся в каждом node, а ключи - ничего, кроме ключей поиска. Следующий шаг - вычисление и поддержание размера поддерева в каждом node: мы должны обновить этот параметр после каждого Merge/Split/Add/Remove, но он позволяет нам найти, например, элемент Kth дерева в O (log N).
Когда у нас есть размеры поддерева в каждом node, мы можем отбросить ключи и представить, что treap представляет массив пользовательских данных в обходном пути. Индекс массива каждого элемента можно легко вычислить из размеров поддеревьев. Теперь мы можем добавить/удалить элемент в середине массива или разделить этот массив - все в O (log N).
Мы также можем выполнить "множественную" операцию - например, добавить постоянное значение ко всем элементам нашего "массива". Чтобы реализовать это, мы должны сделать эту операцию задерживаемой, добавить параметр в каждый node, который представляет задержанную константу, которая должна быть "позже" добавлена ко всем элементам этого подмашины node и "нажимать" изменения по мере необходимости. Добавление константы для подмассива или рисования (маркировки) может быть отложено таким подзаданием, как изменение субарара (здесь отложенная информация в node в бит "подмассива должна быть отменена" ) и т.д.
UPD2: Здесь фрагмент кода - часть небольшого количества информации, которую я нашел. Не замечайте кириллицу:) Слова "с неявным ключом" означают в прямом переводе "с неявным ключом".
