Неявный ключ

Обычное декартово дерево — это структура для множеств, каждый элемент которых имеет какой-то ключ. Эти ключи задают на этом множестве порядок, и все запросы к ДД обычно как-то привязаны к этому порядку.

Но что, если у нас есть запросы, которые этот порядок как-то нетривиально меняют? Например, если у нас есть массив, в котором нужно уметь

1. выводить сумму на произвольном отрезке,
2. «переворачивать» произвольный отрезок, то есть переставлять элементы с $l$ по $r$ в обратном порядке, не меняя остальные.

Если бы не было второй операции, мы бы просто использовали индекс элемента в качестве ключа, но с операцией переворота нет способа их быстро поддерживать актуальными.

Решение такое: выкинем ключи, а вместо них будем поддерживать информацию, которая поможет неявно восстановить ключ, когда он нам будет нужен. А именно, будем хранить вместе с каждой вершиной размер её поддерева:

struct Node {
    int prior, size = 1;
    //         ^ размер поддерева
    // ...
};

Тогда ключ (позицию элемента) можно восстановить как число элементов, которые находятся слева от него — что можно пересчитывать во время спуска по дереву.

Размеры поддеревьев будем поддерживать по аналогии с суммой — напишем вспомогательную функцию, которую будем вызывать после каждого структурного изменения вершины.

int size(Node *v) { return v ? v->size : 0; }

void upd(Node *v) { v->size = 1 + size(v->l) + size(v->r); }

Операция merge не меняется, так как нигде не использует ключи, а вот в split нужно использовать позицию корня вместо его ключа. Про split теперь удобнее думать как «вырежи первые k элементов»:

pair<Node*, Node*> split(Node *p, int k) {
    if (!p) return {0, 0};
    if (size(p->l) + 1 <= k) {
        auto [l, r] = split(p->r, k - size(p->l) - 1);
        //                        ^ правый сын не знает количество вершин слева от него
        p->r = l;
        upd(p);
        return {p, r};
    }
    else {
        auto [l, r] = split(p->l, k);
        p->l = r;
        upd(p);
        return {l, p};
    }
}

Всё. Теперь у нас есть клёвая гибкая структура, которую можно резать как угодно, не опираясь на ключи.

#Пример: ctrl+x, ctrl+v

Node* ctrlx(int l, int r) {
    auto [T, R] = split(root, r);
    auto [L, M] = split(T, l);
    root = merge(L, R);
    return M;
}

void ctrlv(Node *v, int k) {
    auto [l, r] = split(root, k);
    root = merge(l, merge(v, r));
}

#Пример: переворот

Вернемся к изначальной задаче: нужно за $O(\log n)$ обрабатывать запросы переворота произвольных подстрок: значение $a_l$ поменять с $a_r$, $a_{l+1}$ поменять с $a_{r-1}$ и т. д.

Будем хранить в каждой вершине флаг rev, который будет означать, что её подотрезок перевернут:

struct Node {
    bool rev;
    // ...
};

Поступим по аналогии с техникой отложенных операций в дереве отрезков — когда мы когда-либо встретим такую вершину, мы поменяем местами ссылки на её детей, а им самим передадим эту метку:

void push(node *v) {
    if (v->rev) {
        swap(v->l, v->r);
        if (v->l)
            v->l->rev ^= 1;
        if (v->r)
            v->r->rev ^= 1;
    }
    v->rev = 0;
}

Аналогично, эту функцию будем вызывать в начале merge и split.

Саму функцию reverse реализуем так: вырезать нужный отрезок, поменять флаг.

void reverse(int l, int r) {
    auto [T, R] = split(root, r);
    auto [L, M] = split(T, l);
    M->rev ^= 1;
    root = merge(L, merge(M, R));
}