Здравствуйте уважаемые codeforcerы! Я читал много информации про декартовые деревья, но так и не могу реализовать декартово дерево по не явному ключу. Если у кого-нибудь имеется код прошу помогите!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
Здравствуйте уважаемые codeforcerы! Я читал много информации про декартовые деревья, но так и не могу реализовать декартово дерево по не явному ключу. Если у кого-нибудь имеется код прошу помогите!
| Название |
|---|



Тут, похоже, не читали?
Я читал и даже реализовывал обычное декартово дерево и знаю как там все работает.) Но просто не могу понять как работает split в неявном декартовом дереве...) И как оно используется. На e-maxxе не очень было понятно.
Представь, что мы просто выкинули ключ x.
Возникает вопрос — как теперь понимать, какая вершина левее какой? Ответ простой — по ссылкам l и r это однозначно восстанавливается. А именно, из следующего логичного соотношения: все элементы поддерева v->l находятся левее элемента v, который находится левее всех элементов поддерева v->r. С помощью этого однозначно определяется порядок на всех вершинах, лежащих в декартовом дереве.
Теперь поймём, что нам это даёт. Это нам, например, даёт возможность обращаться с деревом, как с последовательностью его вершин, упорядоченной слева направо. Теперь положим в каждую вершину дерева какую-нибудь чиселку, например значение w. Декартово дерево теперь будет работать как последовательность этих значений w. Поясню: пусть у нас есть два дерева A и B, соответствующие последовательностям a и b, если мы рассмотрим дерево merge(A, B), то получим дерево, соответствующее последовательности ab, если рассмотрим дерево merge(B, A) — то последовательности ba. Раньше мы имели право мёрджить только деревья, расположенные строго одно левее другого — теперь такого ограничения нет, мы оторвали деревья от абсолютного позиционирования на плоскости.
Теперь осталось понять, что есть операция split. Split должен просто разбивать дерево T на две части — до элемента с номером k и после. Как её реализовывать — тут уже почитай на емаксе, там вполне доходчиво это объяснено.
Большое спасибо! Zlobober. Я очень благодарен! :)
Просто само название "неявный ключ", имхо не особо удачное. Я тоже не понимал что имеется в виду. По факту у нас есть последовательность, которую можно распечатать рекурсивно процедурой
пронумеруем элементы дерева в этом порядке, и эти номера и будут теми самыми "неявными ключами". просто если "явно" нумеровать, т.е. в каждую вершину это число записывать, то их придётся перезаписывать каждый раз при разрывании/склеивании деревьев, поэтому мы вычисляем эти числа, по ходу операций с деревом, используя поле cnt, означающее размер поддерева.
Спасибо! :)