AIOJ

`__gnu_pbds::tree`

Template Parameters

Key: The type of stored elements. To store multiple elements with the same Key, use a method such as std::pair and struct, together with the lower_bound and upper_bound member functions for lookup.
Mapped: The mapping-rule (Mapped-Policy) type. To make the associative container a set, similar to storing elements in std::set, use null_type here; in older versions of g++, use null_mapped_type. To make it a value-bearing set, similar to std::map, use a Value type like std::map<Key, Value>.
Cmp_Fn: A key-comparison functor, such as std::less<Key>.
Tag: Selects the type of underlying data structure; the default is rb_tree_tag. __gnu_pbds provides three different balanced trees:
- rb_tree_tag: a red-black tree; generally, this is the one to use, and the latter two generally have worse performance than a red-black tree
- splay_tree_tag: a splay tree
- ov_tree_tag: an ordered vector tree; it is simply an ordered structure implemented with a vector, similar to implementing a balanced tree with a sorted vector, and its performance depends on whether the data is designed to cause trouble
Node_Update: The node update policy, defaulting to null_node_update; to use the order_of_key and find_by_order methods, use tree_order_statistics_node_update.
Allocator: The space allocator type.

Construction

__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
                 std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;

Member Functions

insert(x): Inserts an element x into the tree and returns std::pair<point_iterator, bool>. The first element represents the iterator to the insertion position, and the second indicates whether insertion succeeded.
erase(x): Deletes an element/iterator x from the tree. If x is an iterator, it returns an iterator pointing to the element after x (if x is end(), it returns end()); if x is a Key, it returns whether deletion succeeded (if it does not exist, deletion fails).
order_of_key(x): Returns the number of elements strictly less than x (using Cmp_Fn as the comparison logic), namely the rank starting from $0$ .
find_by_order(x): Returns the iterator to the element with the rank determined by Cmp_Fn.
lower_bound(x): Returns the iterator to the first element not less than x (using Cmp_Fn as the comparison logic).
upper_bound(x): Returns the iterator to the first element strictly greater than x (using Cmp_Fn as the comparison logic).
join(x): Merges tree x into the current tree and clears tree x (the comparison functions and element types of the two trees must be the same).
split(x,b): Using Cmp_Fn for comparison, elements less than or equal to x belong to the current tree, and the rest belong to tree b.
empty(): Returns whether the tree is empty.
size(): Returns the size.

Note

The join(x) function requires that the key value ranges of the tree being merged and the tree receiving it be disjoint (that is, all values in the merged tree must be either greater than or less than all values in the current tree); otherwise, it throws a join_error exception.

To merge two trees whose value ranges intersect, insert the elements of one tree into the other one by one.

Example

// Common Header Simple over C++11
#include <iostream>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
__gnu_pbds::tree<pair<int, int>, __gnu_pbds::null_type, less<pair<int, int>>,
                 __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;

int main() {
  int cnt = 0;
  trr.insert(make_pair(1, cnt++));
  trr.insert(make_pair(5, cnt++));
  trr.insert(make_pair(4, cnt++));
  trr.insert(make_pair(3, cnt++));
  trr.insert(make_pair(2, cnt++));
  // Elements on the tree: {(1,0), (2,4), (3,3), (4,2), (5,1)}

  auto it = trr.lower_bound(make_pair(2, 0));
  trr.erase(it);
  // Elements on the tree: {(1,0), (3,3), (4,2), (5,1)}

  // Output the first of the element with rank 1 among ranks 0, 1, 2, and 3
  auto it2 = trr.find_by_order(1);
  cout << (*it2).first << endl;  // Output: 3

  // Output its rank
  int pos = trr.order_of_key(*it2);
  cout << pos << endl;  // Output: 1

  // Split trr at it2
  decltype(trr) newtr;
  trr.split(*it2, newtr);
  for (auto i = newtr.begin(); i != newtr.end(); ++i) {
    cout << (*i).first << ' ';  // Output: 4 5
  }
  cout << endl;

  // Merge tree newtr into tree trr; tree newtr is cleared.
  trr.join(newtr);
  for (auto i = trr.begin(); i != trr.end(); ++i) {
    cout << (*i).first << ' ';  // Output: 1 3 4 5
  }
  cout << endl;
  cout << newtr.size() << endl;  // Output: 0

  return 0;
}

Balanced Trees