Splay Tree - Codeforces

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Начал изучать, возникла пара вопросов. Сдал эту задачу, по времени не сильно отличается от декартова. Так ведь и должно быть? Или может у меня не очень эффективная реализация? Второй вопрос по неявному дереву. Операцию merge по-моему можно делать как в обычном дереве, а вот если в обычном дереве split выполняется через splay, то здесь так нельзя. Нужно ли его делать, как в декартовом? Не ухудшит ли это время работы?
UPD: В неявном все как и в обычном, с этим разобрался, спасибо. Тогда другой вопрос. На вики написано, что эту жуть легко персистентной сделать. Может кто знает как?

Комментарии (21)

Написать комментарий?

OutSide

12 лет назад, # |

В дереве по неявному ключу split делается через splay, как еще его делать?

По поводу времени работы — в статье Тарьяна и Слейтора показано, что к каждой вершине, к которой ты касаешься, нужно применять splay, тогда будет амортизировано O(logn) на операцию.

→ Ответить

Perlik

12 лет назад, # ^ |

Просто если делать через splay, как в обычном, то вот что получается:
пусть было дерево (это я не неявные ключи расставил, а просто данные сопутствующие)
    1
   /  \
  4   5
/      \
2       6
\
  3
Пусть мы теперь хотим по ключу 2 отрезать (неявному разумеется), т.е на выходе должны получить в качестве левого дерева 2 — 3. Если через сплей, то найдем 2 и от нее его сделаем, получится такое дерево:
  2
   \
    1
    / \
  4   5
/      \
3       6
В левую часть ответа пойдет 2, а в правую 1 и ее поддерево.

Ты сделал splay неправильно, посмотри сдесь: http://www.cs.princeton.edu/courses/archive/fall07/cos521/handouts/self-adjusting.pdf

страница 656, рисунок (b) zig-zig

Блин, не то дерево из тетради перерисовал. Вот такой результат:
2
\
  4
/  \
3   1
      \
       5
        \
         6

Если резать по неявному ключу 2, то мы должны применить splay к елементу 3, а не 2.

Точно, спасибо.

Неявное тоже медленнее декартова немного.

PavelKunyavskiy

Скорее всего где-то неоптимально написано, или забыли где-то сделать Splay. Хотя по отдельности оно не сильно выигрывает. А вот в более сложных структурах.

Blond

Тоже хочу изучить эту структуру, но столкнулся с трудностями:

Непонятно, как именно называется по-английски вот это "по неявному ключу". Эта идея используется в Rope, но это всё же не то. По-русски кроме е-макса и этой записи в гугле не находится ничего содержательного.
Не мог бы кто-нибудь разбирающийся написать, как выглядят операции split и merge в splay-деревьях по неявному ключу? Моя идея слияния была — просплеить самую правую вершину в левом дереве и самую левую в правом и просто подвесить одну к другой. Но можно же придумать еще много похожих, ну или например просто делать как в декартовом дереве и каждый раз выбирать случайно корень. Про split пока не думал, но там тоже много вариантов, как мне кажется...

Splay дерево по неявному ключу представляется точно так же (смысл тот же), как и декартово по неявному. А декартово неявное можно найти на хабре например, английских статей я тоже не видел таких.
Точно так же, как и в обычном. Ничего не надо случайно выбирать. Merge — просплеить самую правую в левом, и правое дерево просто подвесить как правое поддерево. Split — находим вершину с неявным ключом x, просплеим ее. Отрезаем правое поддерево.

T0RRES

11 лет назад, # |

Кто-то может обьяснить как обрабатывать запросы, связаные с отрезками? И возможно ли это? Например интересно было бы услышать как делать эту, или эту задачи. Хоть по тематике эти задачи даются как для дерамиды, но так как неоднократно писалось что сплей умеет строго больше декартки, то интересно было бы узнать решение с использованием именно сплей дерева.

11 лет назад, # ^ |

По идее реверс такой же, как в декартовом: высплитили, реверснули, вмержили. Единственное — нужно быть очень аккуратным с push'ами во время splay.

Наверно меня сейчас страшно заминусуют, но видимо я не могу понять то что для каждого в этой ветке является элементарным. Как хранить в дереве элементы, при этом как-то упорядоченые по их расположению на отрезках и как при сплеях не потерять эту упорядоченость?

А в чем проблема? Splay устроен так, что не меняет обход дерева в смысле порядка вершин даже.

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

yeputons

Offtopic: а что это умеет сплей, чего не умеет декартово дерева?

Точно знаю, что умеет декартово, но не умеет сплей: одновременный доступ на чтение из нескольких потоков. Splay требуется каждый раз перестраивать, а декартову это нужно только при изменениях.

Амортизироваться в link-cut :)

Где-то слышал, что оно примерно для этого и было придумано.

← Rev. 2 →

На самом деле link-cut это не единственная надстройка. Просто она единственная с которой было не лень разобраться кому-то кто разбирался с Splay и связанным из российских олимпиадников.

P.S. А придумано оно было ради того, чтобы сделать еще одну надстройку над lct и получить быстрый поток.

+14

Так ты же и говорил когда-то:)

Аватар в тему, спасибо. Как ни странно, конкретных задач на это с того времени так и не узнал (кроме упомянутого и тут, и там lct).

Блог пользователя Perlik