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

Копирование декартова дерева
Автор Azret, история, 9 лет назад, По-русски

Всем привет!

Сейчас решал задачу и тут понадобилось реализовать копирование декартова дерева, в частности у меня есть дерево T и его нужно скопировать и смержить в конец двух других деревьев. Возможно ли это сделать без обхода всего дерева?

UPD Пишу на указателях.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Чтобы делать это достаточно эффективно, нужно персистентное декартово дерево. Персистентная структура данных -- это такая, в которой хранятся все предыдущие состояния. При изменении любой вершины она копируется и изменяется только копия, а оригинальная вершина остаётся в прежнем состоянии. Таким образом, копирование -- просто копирование указателя.

Почитать можно, например, тут; наверняка на КФ можно ещё чего-то нарыть.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -67 Проголосовать: не нравится

Если ты такой умный, то почему такой синий?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А если ты такой глупый, почему такой оранжевый?

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Я, будучи синим, сдавал потоки, а будучи фиолетовым — heavy-light decomposition=) Впрочем, сейчас я опять фиолетовый.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится -24 Проголосовать: не нравится

      Я думаю, что CFшные задачи немного отличаются от олимпиадных. Всё-таки олимпиадная задача, это задача на которую выделяется порядка ~1.5-2 часов, а не та которую надо решить за ~20-30 минут ещё наравне с четырьмя аналогичными.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        А почему заминусовали? АСМ-ные задачи действительно ведь отличаются от IOI-стайла — в них чаще нужна смекалочка, а не структуры и данных и хитрые алгоритмы.

        → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      Кто-то (Darooha) сам придумал HLD задолго до того, как стать фиолетовым ;)

      → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Классная ава! Можешь мне такую же сделать?

    → Ответить