Всем привет!
Некоторые из вас могут помнить мою статью про 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
имеет следующие методы:
get_l_child()
— возвращаетnode_iterator
на левого потомка или node_end, если его не существует.get_r_child()
то же самое для правого потомка.get_metadata()
— возвращаетconst reference
на дополнительные данные, хранящиеся в вершине.*
— разыменование. Возвращает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). В ближайшее время я постараюсь найти и решить ещё несколько задач с его помощью и дополнить статью. Если есть задачи, которые по вашему мнению, можно хорошо решить данной структуре — буду рад, если вы выложите их сейчас :)
Three more solved problems with node update policy:
431E - Химический эксперимент : 7498724
Timus 1523. K-inversions : dqYqcY
Timus 1439. Battle with You-Know-Who : stO6Xl
This problem can also be solved using Policy-Update Structure: Infinite Inversions
Here is the submission: code