From 1ac1594eec26e68365f6663220a7bd6eed1ce4ee Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc54.atis-stud.uni-karlsruhe.de>
Date: Tue, 25 Nov 2014 13:06:27 +0100
Subject: stl tree

---
 datastructures/datastructures.tex |   3 +++
 datastructures/stlTree.cpp        |  12 ++++++++++++
 tcr.pdf                           | Bin 174553 -> 177626 bytes
 3 files changed, 15 insertions(+)
 create mode 100644 datastructures/stlTree.cpp

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
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3