Структуры данных на основе деревьев

Так как все элементы в дереве поиска упорядочены по ключу, будем считать, что у нас есть ключ – индекс элемента, постепенно увеличивающийся на 1 слева направо – и вместо номера будем хранить количество элементов в поддереве. Тогда декартово дерево превращается в структуру данных, поддерживающую операции АТД Массив и АТД Список за `O(log N)`.

Основные операции:

template <typename T>
class ITreap {
struct node {
  T v; // значение элемента
  size_t k; // неявный ключ - количество элементов в поддереве
  int y; // случайная высота
  node *left=nullptr, *right=nullptr;
  node(T v) : v(v), k(1), y(rand()) { }
  void update() { k=1+size(left)+size(right); }
};
node *root;
size_t size(node *n) { return n?n->k:0; }
public:
ITreap():root(nullptr) {}
ITreap(const ITreap&)=delete; // запрет копирования
ITreap& operator=(const ITreap&)=delete; // запрет присваивания
~ITreap() { free(root); }
size_t size() const { return size(root); } // размер
...
};

Операции разрезания и слияния останутся почти такими же, но добавится вызов update для пересчета количества элементов в поддереве:

private:
pair<node*, node*> spliti(node* t, size_t k) { // разрезание по количеству
  if (!t || k>=t->k) return {t,nullptr};
  if(k==0) return {nullptr,t};
  size_t l=size(t->left);
  if (l<k) {
    auto [t1,t2]=spliti(t->right,k-l-1);
    t->right=t1;
    t->update();
    return {t,t2};
  } else {
    auto [t1,t2]=spliti(t->left,k);
    t->left=t2;
    t->update();
    return {t1,t};
  }
}
node* merge(node* t1, node* t2) { // слияние
  if(!t2) return t1;
  if(!t1) return t2;
  if (t1->y > t2->y) {
    t1->right=merge(t1->right,t2);
    t1->update();
    return t1;
  } else {
    t2->left=merge(t1,t2->left);
    t2->update();
    return t2;
  }
}

node* find(size_t k) const { // поиск узла по номеру
  node *p=root;
  while(p) {
    int l=size(p->left);
    if(l==k) break;
    else if(k<l) p=p->left;
    else { k-=l+1; p=p->right; }
  }
  return p;
}
void foreach(function<void(T&)> f, node *p) // обход дерева
{
  if(!p) return;
  foreach(f,p->left);
  f(p->v);
  foreach(f,p->right);
}

public:
  T& operator[](size_t k) { // доступ к элементу по индексу
    if(k>=size()) throw runtime_error("Wrong index");
    node *p=find(k);
    return p->v;
  }
  T operator[](size_t k) const { 
    if(k>=size()) throw runtime_error("Wrong index");
    node *p=find(k);
    return p->v;
  }

  void inserti(size_t k, T v) { // вставка
      if(k>size()) throw runtime_error("Wrong index");
      node *m=new node(v);
      auto [t1,t2]=spliti(root,k);
      root=merge(merge(t1,m),t2);
  }
  void erasei(size_t k) { // удаление
      if(k>=size()) throw runtime_error("Wrong index");
      auto [t1,t]=spliti(root, k);
      auto [m,t2]=spliti(t, 1);
      root=merge(t1,t2);
      free(m);
  }
  void foreach(function<void(T&)> f) {
    foreach(f,root);
  }

Пример использования:

int main()
{ ITreap<int> t;
  t.inserti(0,10); // {10}
  t.inserti(1,20); // {10,20}
  t.inserti(1,15); // {10,15,20}
  t.foreach([&](int& v){ cout<<v<<"\n";});
  t[2]=25; // {10,15,25}
  t.erasei(1); // {10,25}
  cout<<t[0]<<"\n";
  cout<<t[1]<<"\n";
}

Если совместить дерево с доступом по ключу и дерево с неявным ключом, то можно определить операции получения ключа по номеру и номера по ключу:

template <typename Key>
class KTreap {
struct node {
  Key x; // ключ
  size_t k; // неявный ключ - количество элементов в поддереве
  int y; // случайная высота
  node *left=nullptr, *right=nullptr;
  node(Key x) : x(x), k(1), y(rand()) { }
  void update() { k=1+size(left)+size(right); }
};
node *root;
...
public:
  KTreap():root(nullptr) {}
  KTreap(const KTreap&)=delete; // запрет копирования
  KTreap& operator=(const KTreap&)=delete; // запрет присваивания
  ~KTreap() { free(root); }
  size_t size() const { return size(root); } // размер
  bool contains(Key k) const; // поиск как у всех BST
  size_t order(Key k) const { // номер элемента по ключу
    size_t ind=0;
    node *n=root;
    while(n)
    { if(k<n->x)
        n=n->left;
      else {
         ind+=size(n->left);
         if(n->x<k) {
           ++ind;
           n=n->right;
         }
         else return ind;
      }
    }
    return -1;
  }
  Key key(size_t k) const { // элемент по номеру
    if(k>=size()) throw runtime_error("Wrong index");
    node *p=find(k);
    return p->x;
  }
  void visit(function<void(Key)> fun) const;
  void insert(Key k);
  void erase(Key k);
  void erasei(size_t k);
};

Операция inserti не применима к этому классу.