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

Декартово дерево
Автор Shtrix, 16 лет назад, По-русски

В довесок добавлю от себя "Где это можно сдать?":
Robotic Sort на Spoj.pl
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Военные учения сдаются и обычным деревом отрезков :) Зато любая задача, которая сдается с деревом отрезков, сдается и декартовым деревом.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Есть еще старая задача про декартовы деревья, правда она тоже сдается без их использования.
→ Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Есть 1439 на тимусе, там довольно красивый изврат на декартовом дереве.
    → Ответить
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Ее я тоже без деревьев сдавал, просто поддерживал вектор отрезков. Работает не быстро, но все-равно проходит, ну а реализация намного проще.
      → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Оно да, но с декартовым деревом там именно красивый трюк, решающий задачу. Если хочется хорошо владеть декартовым деревом - эта задача будет очень полезна.
        → Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Тогда зачем оно вообще надо? Или какой то класс задач только может покрыть?
→ Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    *только оно
    → Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Не знаю как насчет только оно.

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

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

    Несколько примеров задач которые вроде как не решаются без деревьев поиска привести не сложно.
    → Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +12 Проголосовать: не нравится
    Декартово дерево с явным ключом в основном нужно если в сете нужно найти k-ый элемент или если пишешь на каком-нибудь Паскале (по сути это ручная реализация сета). А декартово дерево с неявным ключом это вообще супер вещь. Позволяет такие крутые штуки делать за log(n), что извлечение минимума, максимума, суммы кажется детской забавой.
    → Ответить
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

      → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Реверс массива/подмассивов за логарифм.
        Циклический сдвиг массива за логарифм.
        Склейка массивов за логарифм.
        ...etc
        Это все декартово дерево по неявному ключу.

        Кстати, вот еще задачка, вы просили: Genetics. Тут и авторское решение предполагало декартово дерево.
        → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Ну в джаве наверное TreeSet не поможет k-ый элемент искать?
        → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        k-ю статистику можно искать и за logN с деревом отрезков. Правда что так, что с фенвиком можно делать только если значение заранее известные, а для декартова дерева это не обязательно.
        → Ответить
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          На самом деле дерево отрезков тоже можно написать так чтобы оно было онлайн-структурой. Но это значительно труднее.
          → Ответить
          • 16 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится
            А разве после этого оно не становится линейным по сложности?
            → Ответить
            • 16 лет назад, скрыть # ^ |
               
              Проголосовать: нравится 0 Проголосовать: не нравится
              Просто изначально у нас одна вершина. Она покрывает все. Теперь вдруг понадобилось обратиться к части отрезка какой-то вершины. Создаем ей 2 потомков и идем в нужного.

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

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

              Откуда взяться линии?
              → Ответить
              • 16 лет назад, скрыть # ^ |
                 
                Проголосовать: нравится 0 Проголосовать: не нравится
                При модификации. Как ты добавишь элемент не перестраивая все дерево?
                → Ответить
                • 16 лет назад, скрыть # ^ |
                   
                  Проголосовать: нравится 0 Проголосовать: не нравится
                  Видимо мы имеем в виду разные вещи. 

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

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

                  Пожалуй эту ветку не стоит продолжать так как ничего не будет видно.Стоит продолжить в основной ветке если это необходимо 
                  → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        log2(n) во многих задачах не проходит
        → Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Еще одно очень мощное применение это дерево эйлерова обхода. Не раз выручало в задачах на изменяющиеся деревья.
→ Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Нифига себе. Не раз... Я такую задачку только на межнаровских сборах видел. А можно ссылки на пару задачек на дерево эйлерова обхода?
    → Ответить
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Согласен. Не раз не совсем подходящее выражение. Но что несколько раз выручало сказать точно могу.

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

      Кроме того иногда деревом обхода можно заменить что-то более простое, если это простое не придумалось.
      → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        В сборах плохое то, что я там был только один раз. А задачки на эйлеров обход больше не встречались. А порешать бы хотелось...
        → Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Если кому интересно - часть 2.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -20 Проголосовать: не нравится
Здесь написано что декартово дерево это структура Наливайко, а в вики указан источник: Seidel, Raimund; Aragon, Cecilia R. «Randomized Search Trees»
Что именно придумал Наливайко? Можно ли где-то найти его книгу или статью?

→ Ответить
»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -6 Проголосовать: не нравится

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

→ Ответить
»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить