Advertisement
Jasir

Order statistics tree

Feb 28th, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <ext/pb_ds/assoc_container.hpp> // Common file
  2. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  3. //#include <ext/pb_ds/detail/standard_policies.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef tree<
  9. int,
  10. null_type,
  11. less<int>,
  12. rb_tree_tag,
  13. tree_order_statistics_node_update>
  14. ordered_set;
  15.  
  16. int main(){
  17.     ordered_set X;
  18.     X.insert(1);
  19.     X.insert(2);
  20.     X.insert(4);
  21.     X.insert(8);
  22.     X.insert(16);
  23.  
  24.     cout<<*X.find_by_order(1)<<endl; // 2
  25.     cout<<*X.find_by_order(2)<<endl; // 4
  26.     cout<<*X.find_by_order(4)<<endl; // 16
  27.     cout<<(end(X)==X.find_by_order(6))<<endl; // true
  28.  
  29.     cout<<X.order_of_key(-5)<<endl;  // 0
  30.     cout<<X.order_of_key(1)<<endl;   // 0
  31.     cout<<X.order_of_key(3)<<endl;   // 2
  32.     cout<<X.order_of_key(4)<<endl;   // 2
  33.     cout<<X.order_of_key(400)<<endl; // 5
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement