Персистентное декартово дерево по неявному ключу

[mayorovp]

Дирамида и правда напрашивается стать персистентной, алгоритм тоже неплохой, но…

Конструктор копирования, принимающий указатель? Отсутствие деструктора?! link = 0 в конструкторе копирования? Ручной подсчет ссылок?! Да, это и правда ненормальное программирование…

[IlyaSM]

Первоначально данная структура использовалась только на олимпиаде. Поэтому удаление вершины возможно только после вызова метода del для нее, он работает вместо деструктора, точнее только в нем адекватно удаление объекта, что вполне оправдано, на мой взгляд.
Аналогично с ссылками. Да, link = 0, ведь это копия, а не исходная вершина.
С ручным подсчетом согласен, накосячил… Можете подсказать более адекватный вариант?

[mayorovp]

Вариант 1. typedef std::shared_ptr<PersistentTreap> PtrPersistentTreap

Вариант 2 (исключительно для однопоточного доступа)

class PtrPersistentTreap {
    PersistentTreap* ptr;

    void assign(PersistentTreap* newPtr) {
        PersistentTreap* oldPtr = ptr;
        ptr = newPtr;
        if (newPtr) newPtr->link++;
        if (oldPtr && --oldPtr->link == 0) delete oldPtr;
    }
public:
    explicit PtrPersistentTreap(PersistentTreap* ptr = 0) :ptr(0) { assign(ptr); }
    PtrPersistentTreap(PtrPersistentTreap const& other) : ptr(0) { assign(other.ptr); }
    PtrPersistentTreap(PtrPersistentTreap && other) : ptr(other.ptr) { other.ptr = 0; }
    ~PtrPersistentTreap() { assign(0); }

    PtrPersistentTreap& operator = (PersistentTreap* ptr) { assign(ptr); return *this; }
    PtrPersistentTreap& operator = (PtrPersistentTreap const& other) { assign(other.ptr); return *this; }
    PtrPersistentTreap& operator = (PtrPersistentTreap && other) { std::swap(ptr, other.ptr); return *this; }

    PersistentTreap& operator * () const { return *ptr; }
    PersistentTreap* operator -> () const { return ptr; }
};

Вроде ничего не забыл…

Разумеется, в обоих случаях поля left и right должны именно PtrPersistentTreap. Их инициализацию из конструкторов теперь можно и убрать. Функция addLink больше не нужна, как и метод del.

PS да, по поводу link вы правы — там и правда в копии должен стоять ноль. Кстати, хитрая получилась ловушка для любителей умных указателей-велосипедов…

[IlyaSM]

Большое спасибо.

[alexeykuzmin0]

Замечательное объяснение, большое спасибо

[DrReiz]

Не хватает в начале краткого отступления: что такое декартовое дерево и неявный ключ.

[Mingun]

Вам нужна вот эта серия статей.

[Mercury13]

Ну и название — «дерамида».
Первый раз вижу такой перевод английского treap.

[mayorovp]

Ну, «дерамида» все-таки звучит лучше, нежели «дуча» или «курево». А других вариантов вроде как и нет…

[Mercury13]

«Курево» тоже впервые вижу.

[mayorovp]

То есть вы только «дучу» и видели? )

[Mercury13]

Да.

[IlyaSM]

Декартово дерево + пирамида
пирамида = куча

[kokorins]

интересная реализация, но зачем в примере персистентность?

[kokorins]

Поясню вопрос: В примере по ссылке, добавление, удаление вершин реализовано подменой корня, то есть предыдущие копии как таковые не используются и не нужны. Придумать, когда они могут быть нужны мне с ходу не получилось, может быть кто-нибудь может натолкнуть на пример.

Надеялся увидеть, как персистентная дерамида инкапсулирует работу в многопоточной среде, но получается, что необходимо лочить всю дерамиду ради мерджа (ждать нового корня) даже для добавления одного элемента.

[alexeykuzmin0]

Split и Merge возвращают указатели на корни деревьев, что позволяет их куда-нибудь сохранить. А одновременная работа с декартовым деревом едва ли будет когда-нибудь возможна

[kokorins]

Полностью с этим согласен, поэтому и вопрос примера исользования персистентности возник.

[alexeykuzmin0]

Упс, выше я сказал хрень.
Само дерево потому и называется персистентным, что не изменяется, а лишь дополняется при выполнении любых операций, в том числе mergе и split. Соответственно, merge и split можно запускать параллельно, а все остальное лишь базируется на них.
В моем олимпиадном прошлом была задача на персистентное декартово дерево, к сожалению, не могу уже вспомнить

[kokorins]

Зачем часть ссылок на промежуточный мердж и часть ссылок на промежуточный split при параллелной работе?

[alexeykuzmin0]

Ну, персистентность изначально делалась не для того, чтобы поддерживать параллельную работу, так что вполне может быть избыточной.
PS: Задача на персистентное декартово дерево: codeforces.ru/contest/292/problem/E

[mayorovp]

Хм, а зачем тут декартово дерево, да еще и персистентное? Достаточно же дерева интервалов.

[alexeykuzmin0]

Хм, а как?

[mayorovp]

Обновление сверху. Для каждого интервала хранится либо начальный индекс в массиве a, откуда его заполняли, либо признак того, что ожидающих операций копирования нет. Дальше очевидно.

[alexeykuzmin0]

И правда. Надо восстанавливать квалификацию олимпиадника =(

[mayorovp]

Чтобы потом сделать операцию CAS. Правда, задача корректного чтения указателя на объект с одновременным увеличением счетчика ссылок на него же намного сложнее, чем реализация персистентного дерева.

[IlyaSM]

Есть вариант задачи именно на персистентную дерамиду. Но чисто в качестве тренировки на ее написании. В виде нормальной олимпиадной задачи найти сложно. Взято из параллели А ЛКШ этого года. (Задача А)
ejudge.lksh.ru/archive/2014/08/A/statements/A-day02.pdf
Так же есть задача со ВКОШПа 2010-го года, которая решается персистентным деревом отрезков, но так же может быть решена при помощи персистентной дерамиды.
codeforces.ru/gym/100043/attachments