здраствуйте. Как вы можете заметить по моему рейтингу, програмист из меня не очень, поэтому такую структур данных как декартово дерево я писать не очень умею.Я пытался ее понять, но не понял, а потом узнал что в STL есть set который делает как мне казалось все тоже самое.
Однако некоторое время назад я столкнулся с задачей в кормене, что то на подобии: есть мн — во чисел, нужно уметь делать 2 операции: добавить \ извлечь, и узнать к-ое по возрастанию число, как это делать декартовым деревом мне вроде понятно(поддерживать кол — во вершин в левом и правом поддереве от каждой), но как это сделать с помощью stl мне не понятно.Кто нибудь знает? Или возможно какое — то другое решение без деревьев вообще?
И приведите мне если не сложно еще возможно какие то примеры задач не решаемых сет-ом но решаемых декартовым деревом что бы меня окончательно мотивировать его научиться писать.
Мне кажется, сначала стоит вот эту книжку почитать:
Ну без деревьев вообще это вряд ли можно решить. С другой стороны, это можно делать не сбалансированным бинарным деревом, а деревом отрезков или цифровым бором. Ну и, в конце концов, можно использовать спрятанный в недрах GNU C++ STL order_statistics_tree, который позволяет за O(logn) выполнять подобные запросы.
На set'e же это сделать не получится, потому что итераторы в нём bidirectional, следовательно, Random Access с ними будет только за O(n).
Насчёт задач, которые решаются только декартовым деревом — это, насколько мне известно, например, задачи, где нужно переворачивать подотрезки, перемещать их, вырезать и делать прочие нехорошие вещи.
Спасибо.
А можно поподробнее на счет решения деревом отрезков?
Можно. Будем вести массив, над которым оно строится по такому принципу: номер ячейки в массиве — элемент. Значение — присутствует ли элемент в множестве. Стоит заметить, что в этом месте можно легко переходить от обычного множества к мультимножеству, если допускать значения помимо 0 и 1. Пусть M — наибольшее число, которое мы можем обнаружить в множестве.
Таким образом, можно за Θ(logM) (а то и за Θ(1), зависит от способа реализации) проверять, есть ли элемент в множестве, а также за Θ(logM) удалять элемент (декрементируем или обнуляем соответствующую ему ячейку) или добавлять его. Теперь легко заметить, что порядковый номер числа i — это сумма на подотрезке [0..i). А это ДО позволяет найти за Θ(logM). Единственная проблема — необходимость хранить массив размера O(M).
Но мы можем решить эту проблему, добавляя вершины в дерево только когда это необходимо (можно использовать unordered_map, но они медленные. Можно также выделять память динамически с указателями, что быстрее, но всё ещё медленно и можно, наконец, выделять память подобно тому, как это делается в боре, то есть, заранее выделить статический массив размеров порядка Θ(NlogM) и потом каждой вершине приписывать уникальный номер в нём и для каждой вершины хранить информацию о номерах потомков, что, как мне кажется, работает наиболее быстро). Тогда мы добьёмся оценки расхода памяти O(NlogM), что уже, скорее всего, является приемлемым.
Искать элемент по порядковому номеру можно с поддержкой размера поддеревьев, спускаясь от корня вниз и переходя в интересующее нас поддерево подобно тому, как это делается в сбалансированных бинарных деревьях, пока мы не дойдём до какого-то листа.
Если дойдут руки, постараюсь позже раздобыть больше подробной информации об упорядоченных множествах, построенных не на сбалансированных бинарных деревьях и опубликовать об этом статью в блог на кф. Так что, stay tuned =)
Zlobober 2 месяца назад написал, что это дерево работает за линию из-за внезапного
std::distanceв коде. Кстати интересно, что ему ответили разработчики (боюсь, что-нибудь вроде "у нас стадия заморозки, ждите следующей версии")Да, помню об этом, но мне казалось, что речь шла о других деревьях.
Почти только что проверил order_statistics_tree на следующих задачах:
http://acm.timus.ru/problem.aspx?space=1&num=1521
http://acm.timus.ru/problem.aspx?space=1&num=1090
http://acm.timus.ru/problem.aspx?space=1&num=1028
Казалось бы, если всё настолько плохо, почему решения заходят и при этом с достаточно неплохим временем?
UPD: В том сообщении описывается именно операция split. Я, к сожалению, не разбираюсь в тонкостях работы сбалансированных деревьев, но, возможно, в тех задачах, которые ставятся перед order_statistics_tree эта операция просто не является необходимой и линейным является только, собственно, вызов операции split?
Если бы что-нибудь ответили, я бы написал. Молчание.
Сама библиотека Policy-Based Data Structures датируется 2004 годом на сайте с документацией, так что вполне возможно, что за 10 лет не осталось ни одного человека, который читает почтовый адрес, указанный там.
У меня была мысль связаться с кем-нибудь из gcc developer team, дабы найти концы хоть кого-нибудь, кто ответственнен за поддержку и включение этого кода в стандартную поставку компилятора, я даже начал этим заниматься, но пока оно временно застопорилось. Хотя докопаться до истины было бы неплохо...
Грустно, конечно. И всё же, почему на задачах эта структура внезапно работает быстро? Стоит ли это списать на слабые тесты или на особенности реализации или на что-то другое?..
Потому что ты не пользуешься сплитами, вероятно. Вставка/удаление/пересчёт работают за честный логарифм.