stl tree

3 files changed, 15 insertions, 0 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index baa4fec..4f9ad04 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -8,3 +8,6 @@
 
 \subsection{Range Minimum Query}
 \lstinputlisting{datastructures/RMQ.cpp}
+
+\subsection{STL-Tree}
+\lstinputlisting{datastructures/stlTree.cpp}
diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp
new file mode 100644
index 0000000..73472a7
--- /dev/null
+++ b/datastructures/stlTree.cpp
@@ -0,0 +1,12 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+using namespace std; using namespace __gnu_pbds;
+typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
+int main() {
+	Tree X;
+	for (int i = 1; i <= 16; i <<= 1) X.insert(i); // {1, 2, 4, 8, 16}
+	cout << *X.find_by_order(3) << endl; // => 8
+	cout << X.order_of_key(10) << endl; // => 4 = successor of 10 = min i such that X[i] >= 10
+	return 0;
+}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index a680c56..bce134e 100644
--- a/tcr.pdf
+++ b/tcr.pdf