Декартово дерево по неявному ключу: массив с вырезанием и разворотом за логарифм

Если ты умеешь резать и склеивать декартово дерево по позиции и разворачивать отрезок флагом, листай до «Теперь сам».

Как думаешь, можно ли вставить в середину массива быстрее, чем за n

Список Python вставляет в середину за Θ(n): все элементы правее сдвигаются. Связный список вставляет за O(1), но до середины ещё надо дойти - Θ(n) шагов. Текстовый редактор с файлом на миллион строк, плейлист с перетаскиванием песен, последовательность ДНК, которую режут и склеивают кусками, - везде нужны и доступ по номеру, и правка в середине.

Прежде чем читать дальше, попробуй угадать: какая из известных тебе структур умеет найти k-й по порядку элемент за логарифм? Если вспомнил размеры поддеревьев - половина урока у тебя уже есть.

На что это похоже

Книга, разрезанная на главы и сшитая обратно. Чтобы переставить главу 7 в начало, никто не переписывает книгу: её разрезают в двух местах, перекладывают кусок и сшивают. Номера страниц после этого никто не хранит - их пересчитывают, когда открывают книгу: «до этой главы столько-то страниц». Декартово дерево по неявному ключу так и устроено: элементы не помнят свою позицию, она каждый раз складывается из размеров того, что лежит левее.

Механизм: размер, split и merge

узел: значение x, случайный приоритет, size (узлов в поддереве), rev
позиция узла = size его левого поддерева + для каждого предка,
              от которого пошли вправо, size(левого ребёнка) + 1

split(t, k):  первые k элементов | остальные
    sz(t.l) < k  →  корень и всё левое - в первую часть;
                    режем правое поддерево по k − sz(t.l) − 1
    иначе        →  корень и всё правое - во вторую часть;
                    режем левое поддерево по k

merge(a, b):  все из a левее всех из b
    корнем становится тот из корней, у кого приоритет выше,
    рекурсия идёт в его правого (корень из a) или левого (из b) ребёнка

Оба прохода идут по ОДНОМУ пути от корня вниз, поэтому стоят столько, сколько глубина дерева - а у декартова дерева со случайными приоритетами она O(log n) в ожидании. Ключей в узлах нет: split ориентируется по размерам, merge - по договорённости «a левее b», поэтому порядок по позициям сохраняется сам. После любого изменения детей узел пересчитывает size = 1 + size(l) + size(r). Для суммы добавляется поле total = x + total(l) + total(r), у пустого дерева сумма 0. Разворот меняет порядок слагаемых, но сохраняет сумму: флаг rev поле total не меняет. Для других свёрток это надо проверять отдельно: например, строка при развороте меняется.

Остальное - сборки из двух деталей:

вставить x на позицию p:   a, b = split(t, p);   merge(merge(a, [x]), b)
удалить позицию p:         a, b = split(t, p);   _, c = split(b, 1)
                           merge(a, c)
развернуть позиции l..r−1: a, b = split(t, l);   m, c = split(b, r − l)
                           m.rev ^= 1;           merge(merge(a, m), c)

Флаг rev означает «всё поддерево надо развернуть». Развернуть дерево - это поменять местами левого и правого ребёнка у КАЖДОГО узла; вместо этого флаг ставят только корню, а когда операция заходит в узел, она сначала проталкивает флаг: меняет детей местами и переключает флаг у них. Это та же отложенная работа, что в дереве отрезков из прошлого урока.

Правило

Декартово дерево по неявному ключу хранит последовательность: ключ узла - его позиция, она вычисляется по размерам левых поддеревьев. Все операции собираются из split(t, k) (первые k и остальные) и merge(a, b) (всё из a левее всего из b); оба идут по одному пути и стоят O(log n) в ожидании. Вставка, удаление и перенос одного непрерывного куска - постоянное число split и merge. Для перестановки многих отдельных кусков надо учесть их число. Групповые операции над отрезком (разворот, прибавление) делаются флагом в корне вырезанного куска и проталкиваются к детям при каждом заходе в узел.

Разбор: split по позиции

Слово ПРИВЕТ (позиции 0..5), приоритеты подобраны так, что дерево такое:

              В  (size 6, приоритет 90)
           /     \
     Р (size 3)    Т (size 2)
     /     \       /
    П       И     Е

split(корень, 2) - отделить «ПР»:
  В:  sz(левое) = 3 ≥ 2 → В уходит вправо, режем левое поддерево по 2
  Р:  sz(левое) = 1 < 2 → Р уходит влево, режем правое по 2 − 1 − 1 = 0
  И:  sz(левое) = 0 ≥ 0 → И уходит вправо, режем пустое левое по 0
  обратный ход: у Р правым ребёнком становится пусто → [П Р]
                у В левым ребёнком становится И     → [И В Е Т]

Затронуты три узла - один путь от корня. Ни одной позиции не хранилось, а разрез прошёл ровно между вторым и третьим элементом.

Разбор: тысяча, десять тысяч, сто тысяч элементов

Сумму отрезка получаем двумя split: выделяем [l, r), читаем total его корня, затем возвращаем три части на место двумя merge. При l = r выделенное дерево пусто, ответ 0. Время - O(log n) в ожидании, поскольку обходить элементы отрезка не нужно.

Программа сначала показывает сумму до и после разворота, а затем держит последовательность в декартовом дереве и параллельно в обычном списке, выполняет по 3000 случайных вставок, удалений и разворотов отрезков, в конце сверяет дерево со списком и считает, сколько узлов в среднем посетила операция и сколько элементов список переместил при вставках, удалениях и разворотах. Финальный обход для сверки не входит в счётчик операций; это проверка, а не часть алгоритма.

import random

rng = random.Random(11)
shagi = 0


class Uzel:
    def __init__(self, x):
        self.x, self.pri = x, rng.random()
        self.l = self.r = None
        self.size, self.rev = 1, False
        self.total = x


def sz(t):
    return t.size if t else 0


def summa(t):
    return t.total if t else 0


def protolknut(t):                 # отложенный разворот - детям
    global shagi
    shagi += 1
    if t.rev:
        t.l, t.r = t.r, t.l
        for d in (t.l, t.r):
            if d:
                d.rev = not d.rev
        t.rev = False


def obnovit(t):
    t.size = 1 + sz(t.l) + sz(t.r)
    t.total = t.x + summa(t.l) + summa(t.r)


def split(t, k):                   # первые k элементов | остальные
    if not t:
        return None, None
    protolknut(t)
    if sz(t.l) < k:
        a, b = split(t.r, k - sz(t.l) - 1)
        t.r = a
        obnovit(t)
        return t, b
    a, b = split(t.l, k)
    t.l = b
    obnovit(t)
    return a, t


def merge(a, b):                   # все из a левее всех из b
    if not a or not b:
        return a or b
    if a.pri > b.pri:
        protolknut(a)
        a.r = merge(a.r, b)
        obnovit(a)
        return a
    protolknut(b)
    b.l = merge(a, b.l)
    obnovit(b)
    return b


def vstavit(t, pos, x):
    a, b = split(t, pos)
    return merge(merge(a, Uzel(x)), b)


def udalit(t, pos):
    a, b = split(t, pos)
    _, c = split(b, 1)
    return merge(a, c)


def razvernut(t, l, r):            # развернуть позиции l..r−1
    a, b = split(t, l)
    m, c = split(b, r - l)
    if m:
        m.rev = not m.rev
    return merge(merge(a, m), c)


def summa_otrezka(t, l, r):       # сумма на [l, r), 0 <= l <= r <= n
    a, b = split(t, l)
    m, c = split(b, r - l)
    otvet = summa(m)
    return merge(merge(a, m), c), otvet


def v_spisok(t, out):
    if t:
        protolknut(t)
        v_spisok(t.l, out)
        out.append(t.x)
        v_spisok(t.r, out)
    return out


t = None
for x in [2, 7, 1, 8, 2, 8]:
    t = merge(t, Uzel(x))
t, do = summa_otrezka(t, 1, 4)
t = razvernut(t, 1, 5)
t, posle = summa_otrezka(t, 1, 4)
t, pustoj = summa_otrezka(t, 2, 2)
print("сумма [1, 4):", do, "после разворота [1, 5):", posle)
print("пустой отрезок:", pustoj, "весь массив:", summa(t))

rng = random.Random(11)
for n in (1000, 10000, 100000):
    t, ref = None, list(range(n))
    for x in ref:
        t = merge(t, Uzel(x))
    shagi = perenosy = 0
    for op in range(3000):
        i = rng.randrange(len(ref))
        j = rng.randrange(i, len(ref)) + 1
        perenosy += (j - i if op % 3 == 2
                   else len(ref) - i - (op % 3 == 1))
        if op % 3 == 0:
            t = vstavit(t, i, -op)
            ref.insert(i, -op)
        elif op % 3 == 1:
            t = udalit(t, i)
            del ref[i]
        else:
            t = razvernut(t, i, j)
            ref[i:j] = ref[i:j][::-1]
    visits = shagi          # обход сверки не относится к операциям
    assert v_spisok(t, []) == ref
    assert summa(t) == sum(ref)
    print(f"n={n:6}: дерево {visits / 3000:4.0f} узлов на операцию,"
          f" список {perenosy / 3000:6.0f} перемещений")

сумма [1, 4): 16 после разворота [1, 5): 11
пустой отрезок: 0 весь массив: 28
n=  1000: дерево   35 узлов на операцию, список    417 перемещений
n= 10000: дерево   49 узлов на операцию, список   4158 перемещений
n=100000: дерево   64 узлов на операцию, список  41211 перемещений

В [2, 7, 1, 8, 2, 8] сумма [1, 4) равна 16. Разворот [1, 5) даёт [2, 2, 8, 1, 7, 8], и та же сумма теперь 11. Общая сумма 28 сохранилась, хотя сумма по прежним позициям изменилась. Это и проверяет согласованность ленивого разворота со свёрткой total.

Сверка дерева со списком прошла на всех трёх размерах. Счётчики сравнивают посещения узлов и перемещения элементов, а не время: у одного посещения и одного сдвига разная цена. Рост последовательности в сто раз увеличил число посещений меньше чем втрое; число перемещений списка выросло примерно в сто раз.

Что ломается без этого

Первая ошибка - забыть пересчитать size после изменения детей: позиции начинают врать, и split режет не там, причём без всякой ошибки - просто элементы уезжают на другие места. Вторая - забыть протолкнуть флаг перед тем, как смотреть на детей: split спускается в «левое» поддерево, которое по смыслу уже правое, и вырезает не тот кусок. Третья - склеивать merge(a, b), когда элементы a не левее элементов b (например, перепутав порядок аргументов): дерево молча хранит уже другую последовательность. Четвёртая - брать неслучайные приоритеты (номер вставки): дерево вырождается в список, и всё снова стоит Θ(n).

Зачем это в работе

Последовательности, которые режут и склеивают, встречаются чаще, чем кажется: текстовые редакторы хранят текст в деревьях кусков (rope), чтобы вставка в гигабайтный файл не копировала гигабайт; плейлисты и списки задач с перетаскиванием; разворот отрезка - ключевой ход в эвристике 2-opt для задачи коммивояжёра, где маршрут разворачивают тысячи раз. В олимпиадных задачах «массив с вырезанием, вставкой и разворотом отрезков» - это почти всегда декартово дерево по неявному ключу.

Теперь сам

Последовательность 0 1 2 3 4 5 6 7. Выполни через split и merge: вырезать кусок с позиции 2 по позицию 4 включительно и вставить его в конец. Сколько вызовов split и merge нужно и что получится?