Предисловие

Перед чтением данной статьи настоятельно рекомендуется прочитать статью про ДД по явному ключу.

В чём идея

Раньше элементы в нашем дереве были упорядочены по их ключу $x$. Однако иногда нам хочется иметь динамический массив с какими-то дополнительными возможностями. В теории можно было бы хранить в каждой вершине не только ключ, но и индекс вершины, и упорядочивать дерево по индексу, но тут возникает проблема: поддерживать все эти индексы слишком сложно и долго.

Решение

Будем хранить не индекс элемента в массиве, а размер дерева. Оказывается, что по этой информации можно находить и индекс элемента: и правда, индекс элемента $t$ в дереве с корнем в $t$ равен size(t->l). Таким образом индекс произвольной вершины можно найти спуском к ней: если она в левом поддереве, то спустимся в левое поддерево, а если в правом - запомним размер левого поддерева, спустимся в правое, посчитаем индекс и прибавим к нему сохранённый размер (потому что все элементы левого поддерева заведомо идут раньше всех элементов правого). Такая модификация позволяет нам изменить $split$: вместо значения будем передавать индекс и делить массив на два по этому индексу.

Реализация

Для поддержания размера создадим две вспомогательные функции: upd и size:

int size(node* t) {
    if (t == nullptr) return 0;
    return t->size;
}

void upd(node* t) {
    if (t == nullptr) return;
    t->size = size(t->l) + size(t->r) + 1;
}

Будем вызывать upd для каждой вершины, которую мы возвращаем, чтобы поддерживать все размеры актуальными.

Новый split будет выглядеть так:

pair<Node*, Node*> split(Node* t, int k) {
    if (t == nullptr) {
        return {nullptr, nullptr};
    }
    int i = size(t->l) + 1;
    if (i < k) {
        auto [tl, tr] = split(t->r, k - i);
        t->r = tl;
        upd(t);
        upd(tr);
        return {t, tr};
    } else {
        auto [tl, tr] = split(t->l, k);
        t->l = tr;
        upd(tl);
        upd(t);
        return {tl, t};
    }
}

Примеры

Помимо того, что мы теперь умеем произвольным образом разрезать массив и можем, например, за $O(logn)$ переместить произвольный отрезок массива в начало или конец - мы можем делать и что-то более интересное. Например: разворот подотрезка. Для его реализации будем хранить в каждой вершине флаг, развёрнуто ли это дерево. Перед любыми изменениями дерева будет пушить разворот: если текущее дерево надо развернуть - поменяем местами его левое и правое поддеревья и у каждого из них поменяем флаг.

Сама функция push будет выглядеть примерно так:

void push(node* t) {
    if (t->rev) {
        t->rev = false;
        swap(t->l, t->r);
        if (t->l != nullptr) {
            t->l->rev ^= 1;
        }
        if (t->r != nullptr) {
            t->r->rev ^= 1;
        }
    }
}

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