Всем привет! После достаточно долгого затишья, я решил, что мой вклад растёт слишком медленно пришёл час порадовать вас ещё одной статьёй в блоге :)

2 месяца назад пользователь Perlik выложил статью, в которой описал очень интересную реализованную в STL структуру, которая позволяла очень быстро производить различные операции с подстроками. Некоторое время после этого я тестировал её на различных задачах и, к сожалению, как правило, получал негативный результат — rope оказалась слишком уж медленной, особенно когда речь шла о работе с отдельно взятыми элементами.

На некоторое время я позабыл о той статье. Однако всё чаще я сталкивался с задачами, в которых нужно было реализовать множество, да не простое, а золотое с возможностью узнавать порядковый номер элемента и, напротив, элемент по его порядковому номеру (т.е., порядковую статистику в множестве). Вопрос выполнения этих операций методами стандартной библиотеки достаточно тонкий и актуальный, подтверждением тому можно привести, например, этот и этот блоги. И тут я вспомнил о том, что в комментариях к той статье кто-то упомянул о загадочной структуре данных order statistics tree, которое как раз поддерживает эти две операции и которое как раз реализовано в STL (хотя и только для GNU C++). Тут и началось моё увлекательное знакомство со структурами данных, основанными на политике (policy based data structures), о которых я хочу поведать и вам :)

Итак, приступим. В данной статье я рассмотрю наиболее интересную из реализованных структур — дерево (tree). Нам потребуется подключить следующие библиотеки:

#include <ext/pb_ds/assoc_container.hpp> // Общий файл. 
#include <ext/pb_ds/tree_policy.hpp> // Содержит класс tree_order_statistics_node_update

При более внимательном рассмотрении можно обнаружить, что последние два файла содержатся в библиотеке

#include <ext/pb_ds/detail/standard_policies.hpp>

Пространство имён, с которым нам прийдётся работать в современных версиях носит название __gnu_pbds; Ранее оно называлось pb_ds;

Теперь рассмотрим конкретные структуры.

Шаблон tree имеет следующий вид:

	  template<
	  typename Key, // Тип ключа
	  typename Mapped, // Тип ассоциированных с ключём данных
	  typename Cmp_Fn = std::less<Key>, // Функтор сравнения, должен соответствовать оператору <
	  typename Tag = rb_tree_tag, // Метка, обозначающая тип дерева
	  template<
	  typename Const_Node_Iterator,
	  typename Node_Iterator,
	  typename Cmp_Fn_,
	  typename Allocator_>
	  class Node_Update = null_node_update, // Метка обновления вершин
	  typename Allocator = std::allocator<char> > // Аллокатор
	  class tree;
	

Опытные участники, должно быть, уже заметили, что если инициализировать в шаблоне только первые 2 типа, то мы получим практически точную копию контейнера map. Сразу оговорюсь, что из этого контейнера можно сделать set, для этого нужно просто указать вторым аргументом шаблона тип null_type (в старых версиях null_mapped_type).

А вот параметры Tag и Node_Update в обычном map'e отсутствуют. Рассмотрим их подробнее.

Tag — класс, обозначающий структуру дерева, которое мы будем использовать. В STL реализовано три класса, которые мы можем здесь использовать, это rb_tree_tag, splay_tree_tag и ov_tree_tag. На практике, однако, допустимо использование только красно-чёрного дерева, spay_tree и ov_tree же, по всей видимости, используют при обновлении линейную по времени операцию split, что и лишает их возможности к применению при решении олимпиадных задач.

Node_Update — класс, обозначающий политику обновления инвариантов вершин. По умолчанию он установлен в null_node_update, т.е., дополнительной информации в вершинах не храниться. Кроме этого, в C++ реализована политика обновления tree_order_statistics_node_update, которая, собственно, и несёт в себе необходимые операции. Рассмотрим их. Скорее всего, наилучшим способом задания дерева будет следующий:

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

Если мы хотим получить ассоциативный массив, а не множество, в качестве второго аргумента следует использовать тип, соответствующий значению в этом множестве. По всей видимости, дерево поддерживает все те же операции, что и set (по крайней мере, до этого у меня с ними конфликта не возникало), но кроме этого добавлены две новые функции — это find_by_order() и order_of_key(). Первая возвращает итератор на k-ый по величине элемент (отсчёт с нуля), вторая — возвращает количество элементов в множестве, строго меньших, чем наш элемент. Пример использования:

    ordered_set X;
    X.insert(1);
    X.insert(2);
    X.insert(4);
    X.insert(8);
    X.insert(16);

    cout<<*X.find_by_order(1)<<endl; // 2
    cout<<*X.find_by_order(2)<<endl; // 4
    cout<<*X.find_by_order(4)<<endl; // 16
    cout<<(end(X)==X.find_by_order(6))<<endl; // true

    cout<<X.order_of_key(-5)<<endl;  // 0
    cout<<X.order_of_key(1)<<endl;   // 0
    cout<<X.order_of_key(3)<<endl;   // 2
    cout<<X.order_of_key(4)<<endl;   // 2
    cout<<X.order_of_key(400)<<endl; // 5

Как мне кажется, наличие такой структуры в STL просто замечательно, т.к. оно позволяет ещё сильнее сузить круг задач, в которых реализация какой-нибудь общеизвестной структуры требует порой больше времени, чем придумывание решения. Напоследок хотелось бы сказать о производительности order_statistics_tree в STL. Для этого я приведу следующую таблицу задач, на которых я её тестировал и результаты по ним.

* В последней задаче для реализации решения за O(mlogn) необходим прямой доступ к вершинам дерева. Без него решение работает за O(mlogn*logn).

Как можно из всего этого видеть, order_statistics_tree сравнительно немного отстаёт от рукописных структур, а порой и вовсе их обгоняет. При этом размер кода сокращается значительно. Отсюда можно сделать вывод, что order_statistics_tree — это хорошо и его можно использовать в контестах.

Кроме tree, я также хотел описать здесь trie — реализованный префиксный бор. Однако, меня смутили некоторые аспекты его реализации, сильно ограничивающие его применимость в олимпиадном программировании, в связи с чем его описание я здесь приводить не буду. Если кому-то интересно, он может самостоятельно попытаться узнать об этой структуре больше.

Полезные ссылки:
— Документация по pb_ds
— Тестирование производительности pb_ds
— Помощь с использованием pb_ds
— Демонстрация использования order_statistics_tree
— Демонстрация использования бора с поиском строк, включающих данную строку в качестве префикса
— Операции с интервалами с помощью самописного класса обновления вершин
— Прочие примеры