Rope (23 апреля 2021)

  1. Кодим
    1. Пишем персистентное дерево отрезков.

  2. Интерфейс Rope: insert(i,x), erase(i), get(i), split, merge, rotate
    1. Известные реализации (деревья по неявному ключу): treap, AVL, RB, 2-3
    2. Новые реализацяии: skip-list, splay, корневая

  3. Skip-list
    1. List: умеет делать Add и Del за O(1), если уже известно место; сложности с Find.
    2. Добавим несколько уровней: ссылки вперёд на 2, на 4, на 8 и т.д. (ровно на степень двойки)
    3. Find работает, но после Insert длины (степени двойки) сломаются. Поэтому будем хитрее: каждый элемент есть на уровне выше с вероятностью 1/2.
    4. Find. Add. Del.
    5. Не забыть: (а) фиктивный элемент, общий для всех списков; (б) мы не храним индексы, храним только длины рёбер

  4. Splay-tree
    1. Собственно дерево: add и del, splay = zig-zig + zig-zag + last one.
    2. Вращения: zig-zag = double = 2 signle, zig-zig = 2 single в другом порядке.
    3. time(add) = time(splay) = ∑ time(zig-zig), осталось оценить только амортизированное время zig-zig
    4. Теорема об амортизированном времени работы. Потенциал = ∑ log(Sv) (Sv − размер поддерева).
    5. Более тонкое время работы: ∑ ti = O(∑ ki log(m/ki))

  5. Персистентность и отцы
    1. Отцы не дружат с персистентностью. Но от них почти всегда можно избавиться.
    2. Fat Nodes позволяет поддерживать и отцов тоже.
− Перерыв −
  1. SQRT-decomposition
    1. Простая корневая: минимум на отрезке.
    2. Что делать, если нужно вставлять и удалять элементы? Два разных решения: split/merge; rebuild.
    3. Удобная версия корневой: только split и rebuild.
    4. Отложенные операции: сортированный массив + добавление новых элементов + количество элементов от x до y. Концепция: есть казалось бы неизменяемая структура, сделаем её изменяемой.
    5. Корневая по запросам: более общий взгляд на предыдущую идею.

  2. Статическая оптимальность
    1. Формулировка задачи с вероятностями и матожиданием.
    2. Решение Кнутом за O(n2).