読者です 読者をやめる 読者になる 読者になる

hogloidのブログ

へなちょこ

g++拡張・tree

g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。
細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えます。
CF・TopCoderでは使えます。

用意:
g++の新しそうなやつを使う
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;


宣言:
tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> var_name;
いきなり長いです。さすがにtypedefするべき
keyに順序関係の定義された好きな型を入れてね

使えること:
setでできるものは大体できます。insert,erase,iterator関連・swapなど。
その他に使えるのが、いずれもO(logN)で

  • find_by_order 関数
    • var_name.find_by_order(k) でk番目(0-indexed)のiteratorを返します。
  • order_of_key 関数
    • var_name.order_of_key(key) でkey以上の最初の要素が、treeの中で何番目か返します。

が使えます。
このおかげで自前で何かを書く手間が省けるときもあるかも?

実は

  • split 関数
    • var_name.split(key,tree) でkey以降の要素をtreeに移す
  • join 関数
    • var_name.join(tree) でtreeを後ろにくっつける

という関数もありますが、どうやら変な実装のせいでO(N)かかるそうです。(少しテストしてみたところメチャクチャ遅かった)

同じkeyは複数保持できません。
null_type を別の型にすると、keyに紐付けされた別の要素を保存できます。

tree_order_statistics_node_updateのところを自前で欲しい要素を付け足した関数オブジェクトを書くと、例えば平衡二分探索木を使ったRMQなどが実現できますが、やっぱりsplitとjoinのせいで使え無さそう。

参考ページ
Implicit cartesian tree in GNU C++ STL. - Codeforces
C++ STL: Policy based data structures - Codeforces