Loading [MathJax]/jax/output/CommonHTML/jax.js
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

RBST Set

コードについての説明

Randomized binary search tree (乱択平衡二分探索木) を用いたランダムアクセス可能な set の実装である. deterministic に深さが O(logn) になる平衡二分探索木(AVL 木や赤黒木など)とは異なり, 木をマージする際にそれぞれの木のサイズに比例した確率で片方の木の根をもう一方の木の根につけるかを決めるという randomize をおこなっている(同様のコード).
GNU C++ の標準ライブラリには赤黒木があるらしいがどうみても使いにくそうだし、それにあまり速くないみたい(参考)
経験上, Splay Tree の方が速くなることが多い気がする.

時間計算量: 各関数 O(logn) (期待計算量)

コード

  1. template <typename T> class RBST {
  2. private:
  3. struct node{
  4. T val;
  5. node *left, *right;
  6. int st_size; // 部分木のサイズ
  7. node(){}
  8. node(T v) : val(v), left(nullptr), right(nullptr), st_size(1){}
  9. ~node() { delete left; delete right; }
  10. };
  11. node *root;
  12. using pnn = pair<node*,node*>;
  13. int size(node* t) { return t ? t->st_size : 0; }
  14. node* update(node *t) {
  15. node* l = t->left; node* r = t->right;
  16. t->st_size = size(l) + size(r) + 1;
  17. return t;
  18. }
  19. unsigned rnd(){
  20. static unsigned x = 123456789, y = 362436069, z = 521288629, w = 86675123;
  21. unsigned t = (x^(x<<11));
  22. x = y,y = z,z = w;
  23. return (w = (w^(w>>19))^(t^(t>>8)));
  24. }
  25. node* merge(node* l, node* r){
  26. if (!l || !r) return (!l) ? r : l;
  27. if(rnd() % (size(l) + size(r)) < (unsigned)size(l)){
  28. l->right = merge(l->right, r);
  29. return update(l);
  30. }else{
  31. r->left = merge(l, r->left);
  32. return update(r);
  33. }
  34. }
  35. pnn split(node* t, int k){ //木のサイズが(k,n-k)となるように分割する
  36. if(!t) return pnn(nullptr, nullptr);
  37. if(k <= size(t->left)){
  38. pnn s = split(t->left, k);
  39. t->left = s.second;
  40. return pnn(s.first,update(t));
  41. }else{
  42. pnn s = split(t->right, k-size(t->left)-1);
  43. t->right = s.first;
  44. return pnn(update(t), s.second);
  45. }
  46. }
  47. int lower_bound(node *t, const T k){
  48. if(!t) return 0;
  49. if(t->val < k){
  50. return size(t->left) + lower_bound(t->right,k) + 1;
  51. }else{
  52. return lower_bound(t->left,k);
  53. }
  54. }
  55. void lower_value(node *t, const T k, T& res){
  56. if(!t) return;
  57. if(t->val < k){
  58. lower_value(t->right,k,res);
  59. }else{
  60. lower_value(t->left,k,res=t->val);
  61. }
  62. }
  63. int upper_bound(node *t, const T k){
  64. if(!t) return 0;
  65. if(t->val <= k){
  66. return size(t->left) + upper_bound(t->right,k) + 1;
  67. }else{
  68. return upper_bound(t->left,k);
  69. }
  70. }
  71. void upper_value(node *t, const T k, T& res){
  72. if(!t) return;
  73. if(t->val <= k){
  74. upper_value(t->right,k,res);
  75. }else{
  76. upper_value(t->left,k,res=t->val);
  77. }
  78. }
  79. T get(node *t, int k){
  80. if(!t) assert(false);
  81. int s = size(t->left);
  82. if(s > k) return get(t->left,k);
  83. else if(s < k) return get(t->right,k-s-1);
  84. else return t->val;
  85. }
  86. node* insert(node* t, int k, node* u){
  87. pnn s = split(t, k);
  88. return merge(merge(s.first, u), s.second);
  89. }
  90. pnn erase(node* t, int k){
  91. pnn sr = split(t, k+1);
  92. pnn sl = split(sr.first, k);
  93. return pnn(merge(sl.first, sr.second), sl.second);
  94. }
  95. public:
  96. RBST() : root(nullptr){}
  97. //k以上の数の最小インデックス
  98. int lower_bound(const T k){ return lower_bound(root,k); }
  99. //k以上の最小の数
  100. T lower_value(const T k){
  101. T res = numeric_limits<T>::max();
  102. lower_value(root,k,res);
  103. return res;
  104. }
  105. //kを超える数の最小インデックス
  106. int upper_bound(const T k){ return upper_bound(root,k); }
  107. //kを超える最小の数
  108. T upper_value(const T k){
  109. T res = numeric_limits<T>::max();
  110. upper_value(root, k, res);
  111. return res;
  112. }
  113. //値valを挿入
  114. void insert(T val){
  115. root = insert(root, upper_bound(val), new node(val));
  116. }
  117. //値valを削除
  118. void erase(T val){
  119. node *p;
  120. tie(root, p) = erase(root, lower_bound(val));
  121. p->left = p->right = nullptr;
  122. delete p;
  123. }
  124. //k番目の値を返す
  125. T get(int k){ return get(root,k); }
  126. void print(){
  127. int sz = size(root);
  128. rep(i,sz) cout << get(i) << " ";
  129. cout << "\n";
  130. }
  131. };

verify 用の問題

Atcoder : データ構造 提出コード(非想定解)