Декартово дерево

Концепция

Известно, что с одним набором ключей можно построить большое количество различных [деревьев поиска](Деревья поиска), так вот эту проблему можно устранить, добавив некоторой определенности к ключам, например дав каждому в пару приоритет и строя одновременно дерево поиска на ключах и кучу на приоритетах.

Отступление

На самом деле splay-дерево лучше чем декартово во всем, если мы будем сравнивать их как деревья поиска, так что если вы его знаете и декартач вам не нравится, или не заходит по времени, пишите splay.

Идея

Нам не важны приоритеты, которые мы даем ключам, поэтому давайте выдавать случайные приоритеты ключам. Дальше будет доказано, что в таком случае средняя глубина любой вершины будет $O(\log n)$.

Реализация

В декартовом дереве все держится на 2 операциях: split и merge, реализуем их, а потом через них все остальное.

Merge(T1, T2)

Merge - объединение двух деревьев в одно, на деревья наложены ограничения, любой ключ из левого дерева меньше, чем любой ключ из правого. Наша реализация накладывает на нас ограничение: в итоге должна получиться куча на приоритетах, значит мы точно знаем, корнем будет вершина с наибольшим приоритетом, а вторая должна быть смерджена с одним из потомков будущего корня. Сложность работы - $O(h)$.

Код

node *merge(node *l, node *r) {   
  if (l == nullptr) {    
    return r;  
  }  
  if (r == nullptr) {    
    return l;  
  }  
  if (l->y >= r->y) {   
    l->r = merge(l->r, r);     
    return l;  
  }  
  r->l = merge(l, r->l);  
  return r;
}

Усовершенствованный Merge

Классическое дд пишется на приоритетах, но на самом деле от них можно отказаться. Если обозначить как size(T) - размер поддерева T, то в merge мы можем подвешивать левое дерево к правому с вероятностью:

$$\frac{size(R)}{size(L)+size(R)}$$

А правое к левому с вероятностью:

$$\frac{size(L)}{size(L)+size(R)}$$

Заметим, что тогда нам вообще не нужны приоритеты, но нам нужно доказать, что все деревья получаются равновероятно. Хорошо, докажем это для корня, если это сделать, то можно его выкинуть, дд разобъется на 2 и для них все утверждения аналогичны, получим доказательство для всего дерева. Для корня утверждение звучит так:

Лемма. Каждая вершина равновероятно станет корнем.

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

$$\frac{size(L)}{size(L)+size(R)}$$

Значит, раз у всех вершин в нем вероятность стать корнем всего дерева -

$$\frac{1}{size(L)+size(R)}$$

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

Код

node *merge(node *l, node *r) {
  if (!l) {
    return r;
  }
  if (!r) {
    return l;
  }
  if (rnd() % (size(l) + size(r)) < size(l)) {
    l->s_r = merge(l->s_r, r);
    upd_value(l);
    return l;
  }
  r->s_l = merge(l, r->s_l);
  upd_value(r);
  return r;
}

Split(T, x)

Split - разрез дерева на два по такому правилу: вершины с ключом, меньшим x окажутся в левом дереве, с большим - в правом(про равенство обычно не говорят, может быть там, где решит программист). Ну тут все совсем просто, начинаем алгоритм в корне, мы знаем, куда отойдет вершина, от которой мы запустились, а также знаем, куда отойдет поддерево одного из его сыновей, нужно просто запустить split от второго и привязать результат этого на место сына, от которого мы запустились. Сложность работы - $O(h)$.

Код

pair<node *, node *> split(node *root, long long x) {  
  if (root == nullptr) {  
    return {nullptr, nullptr};
  }    
  if (root->x > x) {   
	  auto res = split(root->l, x);  
	  root->l = res.second;
	  upd_value(root);  
	  return {res.first, root}; 
  }
  auto res = split(root->r, x);    
  root->r = res.first;    
  upd_value(root);    
  return {root, res.second};  
}

Остальные операции

Кратко опишу логику остальных операций:

• insert (в начало/конец) - merge
• insert (в любое место) - split + split + merge + merge
• remove (первый/последний элемент) - split
• remove (отрезка или одной вершины) - split+split+merge Короче, удобно.

Математические свойства объекта

Единственность декартова дерева на заданном наборе пар ключ-значение

Начнем с более скучного факта: для заданного набора пар ключ-приоритет, в котором все ключи и приоритеты разные, декартово дерево строится единственным образом. Сам по себе факт бесполезный, но позволяет лучше понять структуру, с которой мы работаем.

Доказательство:

1. Отсортируем все пары по значению ключа.
2. Заметим, что корень у нас определяется единственным образом - вершина с наибольшим приоритетом.
3. Все вершины левее этого корня будут в поддереве левого сына этой вершины, а вершины правее, наоборот, в поддереве правого сына. Разделим наш отрезок на 2 по этому принципу.
4. Вернемся ко 2ому шагу этого алгоритма, но уже для этих подотрезков. После того, как описанный выше алгоритм закончит работу, он построит декартово дерево на заданном ему наборе пар ключ-значение, так как у нас нигде не было выбора, то построенное дерево будет единственным.

Средняя глубина вершины

Давайте наконец докажем, что все операции в среднем работают за $O(\log n)$, показав, что именно такая средняя глубина вершины в декартовом дереве.

Доказательство: Заметим, что глубина вершины $v$ - кол-во вершин, которые являются предком вершины $v$. Тогда докажем следующую лемму.

Лемма. В декартовом дереве вершина $u$ - предок вершины $v$, если на отрезке $[min(u,v),max(u,v)]$ в массиве пар, отсортированном по ключам - у вершины $u$ максимальный приоритет.

Доказательство:

1. Предположим у вершины $u$ не максимальный приоритет, значит есть другая вершина на этом отрезке с большим приоритетом - $t$.
2. Вспомним прошлое доказательство единственности декартова дерева, в нем мы конструктивно его строили, если мы в том алгоритме остановимся на вершине $t$, что будет раньше, чем для вершины $u$ и $v$, потому что приоритет у $t$ меньше, то мы поймем, что $u$ и $v$ попадут в разные поддеревья, потому что находятся с разных сторон от $t$, а значит $u$ не может быть предком $v$.

Докажем в обратную сторону:

1. Пусть у нас $u$ не предок вершины $v$, но имеет наибольший приоритет на отрезке $[min(u,v),max(u,v)]$, тогда точно есть единственная вершина $t$, для которой верно, что $u$ и $v$ ее потомки, и лежат в поддеревьях разных сыновей этой вершины.
2. Что тогда мы знаем про $t$:
   1. Она лежит между $u$ и $v$, потому что ее ключ между ключами $u$ и $v$.
   2. Ее приоритет больше, чем у $u$ и $v$.
3. Получаем противоречие, есть вершина $t$ на отрезке $[min(u,v),max(u,v)]$ с большим приоритетом, чем у $u$. Вернемся к основному доказательству, так как мы случайно брали приоритеты, то теперь мы знаем вероятность того, что вершина под номером $u$ - предок вершины под номером $v$ - $\frac{1}{|u-v|+1}$. Подсчитаем эту вероятность для вершины под номером $k$:

$$\sum _{i=1}^{k-1}\frac{1}{k-i+1}+\sum _{j=k+1}^n\frac{1}{j-k+1}\le 2\ast \sum _{i=2}^n\frac{1}{i}=2\log n$$

Получили нужную нам асимптотику.

Неявное дд

Концепция

Мы хотим уметь делать то же самое, но на массиве значений, а то есть:

• Быстро объединять массивы
• Быстро вставлять в любое место массива подмассив
• Быстро делить массив на 2 подмассива
• Быстро делать массовые операции
• Быстро находить по ссылке на элемент его индекс в массиве Под быстро тут везде подразумевается асимптотика $O(\log n)$.

Идея

Заметим, что уже почти все готово, нужно просто как-то избавиться от дерева поиска по ключам, и мы получим нужную нам структуру данных. Также подметим, что из двух ключевых операций merge и split, на ключи опирается только split. Так давайте перепишем его так, чтобы теперь он переходил в сына не на основе ключа, который лежит в текущей вершине, а на основе размеров поддеревьев, и мы получим неявное дд. Неявным оно названо, потому что ключ теперь хранится неявно, и это на самом деле размер поддеревьев.

Измененный split

pair<node *, node *> split(node *root, long long k) {  
  if (!root) {  
    return {nullptr, nullptr};  
  }  
  if (size(root->l) >= k) {  
    auto res = split(root->l, k);    
    root->l = res.second;    
    upd_value(root);    
    return {res.first, root};  
  }  
  auto res = split(root->r, k - size(root->l) - 1);  
  root->r = res.first;  
  upd_value(root);  
  return {root, res.second};
}

В этом коде есть загадочные функции upd_value и size, про которые я еще не рассказал. Как я уже говорил выше, теперь мы ориентируемся на размеры поддеревьев, что означает, что нам нужно их где-то хранить, обычно под это заводится отдельное поле у вершины, которое и будет возращать size с проверкой на пустой указатель:

int size(node *x) {  
  if (!x) {  
    return 0;  
  }  
  return x->size;
}

Ну а upd_value занимается тем, что пересчитывает все внутренние переменные через детей при изменении структуры дерева. Это крайне удобно и я очень советую писать именно так, потому что далее будет рассказано про отложенные операции и функцию push, проталкивающую их и очень легко допустить ошибку и объединить эти функции в одну, как, например, происходит в до, и получить потом TL на каком-то хорошем тесте.

void upd_value(node *x) {  
  if (!x) {    
    return;  
  }  
  x->size = 1 + size(x->l) + size(x->r);  
  // Другие обновления через сыновей
}

Ленивое распространение

Идешь в душ, делай push! - Неизвестный мудрец, 201* год

Иногда хочется делать грязь с отрезками, например делать прибавление на них, присвоение, считать сумму, максимум, минимум, реверсить и так далее. Но ручками делать это долго. На помощь придет лень, а точнее ленивое распространение. Пусть у нас есть какая-то операция на отрезке, причем ВАЖНО: для каждой вершины мы знаем все изменения в ней, если эту операцию применить. Тогда давайте пользоваться таким классным свойством, предположим у нас есть вершина дд, отвечающая за отрезок, на котором эту операцию хочется применить. Заведем флажок, который будет обозначать, что нам нужно применить операцию к поддереву этой вершины, а когда посетим эту вершину, сделаем в ней изменения, чтобы получить корректные данные для нее, а флажок протолкнем в детей. Также важно, чтобы эти изменения не обязывали высчитывать промежуточные результаты в вершинах, например, мы можем присвоить значение $x$ потомку не зная, какие изменения были в нем до, что позволяет нам проталкивать флаги нерекурсивно, а просто перезаписывая. Таким образом мы будем насчитывать реальные значения в вершинах мы будем только когда посещаем их и делаем push от них, а значит это не будет увеличивать сложность алгоритма. Теперь чтобы в нашем неявном дд сделать прибавление на отрезке мы можем завести поле add, отвечающие за прибавление на отрезке у поддерева данной вершины, при запросе с помощью двух split’ов получать нужный отрезок, ручками менять поле у его корня и мерджить обратно. Очень удобно. Главное не забывать делать push всегда и везде. Вот его примерный код для сложения с подсчетом суммы на отрезке:

void push(node *x) {  
  if (x == nullptr) {   
     return;  
  }
  if (x->add != 0) {
    x->sum += x->size * x->add;
    if (x->l) {
      x->l->add += x->add;
    }
    if (x->r) {
      x->r->add += x->add;
    }
    x->add = 0;
  }
  // Проталкивание других флагов
}

Персистентное дд

Как и дерево отрезков, дд можно сделать персистентным, для этого вам просто нужно при любом изменении в вершине создавать ее полную копию и делать изменение уже с ней. Просто модифицируйте split и merge так, чтобы они внутри и создавали копии вершин. Тут то и пригождается Усовершенствованный Merge, который я описал чуть выше, если мы напишем обычный, то пользователь сможет много раз смерджить одно и то же дерево, что сломает его, но если мы ободемся без приоритетов, то ломаться оно уже не будет.