Декартово дерево

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

Есть 1439 на тимусе, там довольно красивый изврат на декартовом дереве.

→ Ответить

it4.kp

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

Ее я тоже без деревьев сдавал, просто поддерживал вектор отрезков. Работает не быстро, но все-равно проходит, ну а реализация намного проще.

→ Ответить

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

Оно да, но с декартовым деревом там именно красивый трюк, решающий задачу. Если хочется хорошо владеть декартовым деревом - эта задача будет очень полезна.

→ Ответить

OSt	14 лет назад, # \| 0 Тогда зачем оно вообще надо? Или какой то класс задач только может покрыть? → Ответить

OSt	14 лет назад, # ^ \| 0 *только оно → Ответить

Avalanche

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

Например, задачи на реверс подмассива или своп двух подмассивов.

→ Ответить

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

Не знаю как насчет только оно.

Но я знаю много задач которые с помощью декартового дерева сильно проще придумать и не сильно сложней написать.

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

Несколько примеров задач которые вроде как не решаются без деревьев поиска привести не сложно.

→ Ответить

Edvard

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

+12

Декартово дерево с явным ключом в основном нужно если в сете нужно найти k-ый элемент или если пишешь на каком-нибудь Паскале (по сути это ручная реализация сета). А декартово дерево с неявным ключом это вообще супер вещь. Позволяет такие крутые штуки делать за log(n), что извлечение минимума, максимума, суммы кажется детской забавой.

→ Ответить

OSt

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

Если Вы о поиске k-ой статистики в сете, то можно предложить алгоритм сложности (nLogn)^2 через двоичный поиск и Фенвика.

Усложним задачу - допустим, что у нас ко всему ещё есть библиотека Явы, в котором есть такие чУдные вещи, как TreeSet, TreeMap и прочее.

Что тогда мы можем реализовать только treap'ом?

→ Ответить

Skiminok

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

Реверс массива/подмассивов за логарифм.

Циклический сдвиг массива за логарифм.

Склейка массивов за логарифм.

...etc

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

Кстати, вот еще задачка, вы просили: Genetics. Тут и авторское решение предполагало декартово дерево.

→ Ответить

OSt	14 лет назад, # ^ \| +1 Большое спасибо! Теперь хоть понятно для чего оно может быть полезным. Будем вкуривать :) → Ответить

forest

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

Однако и тут без него легко можно обойтись

→ Ответить

e-maxx

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

Ну в джаве наверное TreeSet не поможет k-ый элемент искать?

→ Ответить

KADR	14 лет назад, # ^ \| 0 k-ю статистику можно искать и за logN с деревом отрезков. Правда что так, что с фенвиком можно делать только если значение заранее известные, а для декартова дерева это не обязательно. → Ответить

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

На самом деле дерево отрезков тоже можно написать так чтобы оно было онлайн-структурой. Но это значительно труднее.

→ Ответить

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

А разве после этого оно не становится линейным по сложности?

→ Ответить

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

Просто изначально у нас одна вершина. Она покрывает все. Теперь вдруг понадобилось обратиться к части отрезка какой-то вершины. Создаем ей 2 потомков и идем в нужного.

Всего мы обратились к Nlog вершинам за все время ибо дерево отрезков. И время на это очевидно nlog.

Количество вершин тоже nlog.

Откуда взяться линии?

→ Ответить

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

При модификации. Как ты добавишь элемент не перестраивая все дерево?

→ Ответить

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

Видимо мы имеем в виду разные вещи.

Поясню что имею ввиду я.

У нас дерево покрывает большой отрезок. Отрезок большой. Поэтому не получается хранить все вершины. Значит храним только полезные - те которые нам когда-то были нужны или только что понадобились.

таких мало.

Пожалуй эту ветку не стоит продолжать так как ничего не будет видно.Стоит продолжить в основной ветке если это необходимо

→ Ответить

Edvard

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

log²(n) во многих задачах не проходит

→ Ответить

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

Еще одно очень мощное применение это дерево эйлерова обхода. Не раз выручало в задачах на изменяющиеся деревья.

→ Ответить

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

Нифига себе. Не раз... Я такую задачку только на межнаровских сборах видел. А можно ссылки на пару задачек на дерево эйлерова обхода?

→ Ответить

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

Согласен. Не раз не совсем подходящее выражение. Но что несколько раз выручало сказать точно могу.

А что плохого в сборах?

Кроме того иногда деревом обхода можно заменить что-то более простое, если это простое не придумалось.

→ Ответить

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

В сборах плохое то, что я там был только один раз. А задачки на эйлеров обход больше не встречались. А порешать бы хотелось...

→ Ответить

Skiminok

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

Если кому интересно - часть 2.

→ Ответить

Trytrytry

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

-20

Здесь написано что декартово дерево это структура Наливайко, а в вики указан источник: Seidel, Raimund; Aragon, Cecilia R. «Randomized Search Trees»

Что именно придумал Наливайко? Можно ли где-то найти его книгу или статью?

→ Ответить

Jokser

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

+39

Фигня это. На самом деле все структуры придумал Макс Иванов :)

→ Ответить

DaurenMuratov

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

← Rev. 2 →

-6

В задаче с роботом, как там строить неявное декартово дерево ? У меня проблема в нахождение индексов элементов, то-есть где именно находиться элемент в данном массиве, ведь ключом дерева являются индексы, а не сами элементы. ???

→ Ответить

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

← Rev. 2 →

Не подскажете, где можно сдать что-то без включения мозга, тупо на написание того, что надо сделать на ДД. конкретно интересуют какие-то модификации на отрезке (увеличение/присваивание/разворот? на отрезке), запрос суммы/минимума/максимума на отрезке

→ Ответить

imslavko

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

← Rev. 2 →

COCI — хорватские олимпиады. Имя задачи -- "upit".

→ Ответить

http://informatics.mccme.ru/inf/view_by_subject_new.php?parent=90&start=0 http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1974

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

Ур-ра заррработало!:)

Спасибо, сдал

→ Ответить

yarrr

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

← Rev. 2 →

→ Ответить

Zlobober

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

← Rev. 2 →

Сдай задачу UPIT с COCI #7 за прошлый год. Это всё в одном флаконе.

UPD: блин, смотрю не одному мне эта задача запомнилась)))

→ Ответить

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

А как там сдавать? А то я что-то туплю)

→ Ответить

Zlobober

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

Никак, тесты даны, чекера не надо — ответ однозначный.

→ Ответить

imslavko

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

тесты скачать и локально проверить

→ Ответить

agul

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

+29

Ты и Zlobober мысли друг друга читаете? :)

→ Ответить

Tranvick

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

← Rev. 2 →

А как там адекватно второй запрос обрабатывать? Без него все просто.
По поводу где сдать — на dl.gsu.by можно сдать все COCI до ноября 2011.

→ Ответить

Zlobober

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

← Rev. 2 →

Следующим образом. Держим не только значение в вершине с кучей модификаторов, но и особый модификатор L. Он собой символизирует линейный прирост к значению от номера вершины в дереве i. То есть значение в вершине будет A + i * L. Понятно, что вот эту константу L можно как-то при желании пересчитывать.

→ Ответить