Всем привет!

Некоторые из вас могут помнить мою статью про policy based data structures. Кроме обзорной статьи на эти структуры, я также хотел написать про возможность использования самописного Node_Update в структуре. Тогда мне так и не удалось выделить на это достаточно времени, однако теперь я могу и хочу наверстать упущенное и поделиться с вами новыми знаниями.

Итак, начнём. Шаблон класса обновления вершин должен иметь следующий вид:

template<class Node_CItr,
	 class Node_Itr,
	 class Cmp_Fn,
	 class _Alloc>
struct my_node_update
{
    typedef my_type metadata_type;

    void operator()(Node_Itr it, Node_CItr end_it)
    {
        ...
    }
};

Рассмотрим то, как работает этот класс подробнее. pb-дерево, использующее политику обновления вершин будет дополнительно хранить в вершине одну переменную типа my_type. Когда дерево перестраивается, часть метаданных портятся, поэтому к каждой вершине, у которой метаданные могли быть испорчены применяется оператор (). При этом начинает он применяться с листьев, то есть, нам гарантируют, что если () применяется к вершине, то её метаданные могут быть испорчены, но метаданные её потомков будут целы. Функция имеет два аргумента — познакомимся с ними и с их типами.

Node_Itr it — итератор, указывающий на узел, из которого был вызван (). Node_CItr end_it — const-итератор на узел, на который ссылаются все NIL-вершины. Node_iterator имеет следующие методы:

1. get_l_child() — возвращает node_iterator на левого потомка или node_end, если его не существует.
2. get_r_child() то же самое для правого потомка.
3. get_metadata() — возвращает const reference на дополнительные данные, хранящиеся в вершине.
4. * — разыменование. Возвращает reference на обычный итератор данного элемента.

Для ясности привожу пример функции () для поддержки размера поддерева, начинающегося в данной вершине:

    void operator()(Node_Itr it, Node_CItr end_it)
    {
        auto l=it.get_l_child();
        auto r=it.get_r_child();
        int left=0,right=0;
        if(l!=end_it) left =l.get_metadata();
        if(r!=end_it) right=r.get_metadata();
        const_cast<int&>(it.get_metadata())=left+right+1;
    }

Что ж, мы научились обновлять на ходу инварианты. Теперь научимся их использовать. Для этого обратим внимание, что любые public-методы node_update автоматически станут public в нашем дереве. Кроме того, нам доступны все виртуальные методы базового класса, то есть дерева, если мы их также объявляем виртуальными. В связи с этим добавим в наш класс следующие строки:

    virtual Node_CItr
    node_begin() const = 0;
 
    virtual Node_CItr
    node_end() const = 0;

Это даст нам возможность получать прямой доступ к дереву. В частности, node_begin() будет указывать на корень дерева, а node_end() на пространство вне дерева, в котором находятся NIL-вершины. Наконец, всё готово, чтобы целиком управлять метаданными в вершинах нашего дерева. Так, например, будет выглядеть функция, находящая порядковый номер элемента в дереве из int. (безусловно, можно написать её обобщённой, что и сделано в tree_order_statistics_node_update, однако, мы предполагаем, что будем использовать её в олимпиадной задаче, так что...):

    int order_of_key(int x)
    {
        int ans=0;
        auto it=node_begin();
        while(it!=node_end())
        {
            auto l=it.get_l_child();
            auto r=it.get_r_child();
            if(Cmp_Fn()(x,**it))
            {
                it=l;
            }
            else
            {
                ans++;
                if(l!=node_end()) ans+=l.get_metadata();
                it=r;
            }
        }
        return ans;
    }

В данный момент у меня есть два примера использования своего класса обновления вершин — решение задачи D (7485682) с недавнего контеста и решение задачи НОД2010 с тимуса (sol). В ближайшее время я постараюсь найти и решить ещё несколько задач с его помощью и дополнить статью. Если есть задачи, которые по вашему мнению, можно хорошо решить данной структуре — буду рад, если вы выложите их сейчас :)