updated tcr

24 files changed, 805 insertions, 283 deletions

diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp
new file mode 100644
index 0000000..fe92c7f
--- /dev/null
+++ b/datastructures/LCT.cpp
@@ -0,0 +1,178 @@
+constexpr ll queryDefault = 0;
+constexpr ll updateDefault = 0;
+
+ll _modify(ll x, ll y) {
+	return x + y;
+}
+
+ll _query(ll x, ll y) {
+	return x + y;
+}
+
+ll _update(ll delta, int length) {
+	if (delta == updateDefault) return updateDefault;
+	//ll result = delta
+	//for (int i=1; i<length; i++) result = _query(result, delta);
+	return delta * length;
+}
+
+//generic:
+ll joinValueDelta(ll value, ll delta) {
+	if (delta == updateDefault) return value;
+	return _modify(value, delta);
+}
+
+ll joinDeltas(ll delta1, ll delta2) {
+	if (delta1 == updateDefault) return delta2;
+	if (delta2 == updateDefault) return delta1;
+	return _modify(delta1, delta2);
+}
+
+struct LCT {
+	struct Node {
+		ll nodeValue, subTreeValue, delta;
+		bool revert;
+		int id, size;
+		Node *left, *right, *parent;
+		
+		Node(int id = 0, int val = queryDefault) : 
+			nodeValue(val), subTreeValue(val), delta(updateDefault), 
+			revert(false), id(id), size(1),
+			left(nullptr), right(nullptr), parent(nullptr) {}
+			
+		bool isRoot() {
+			return !parent || (parent->left != this && 
+												 parent->right != this);
+		}
+		
+		void push() {
+			if (revert) {
+				revert = false;
+				swap(left, right);
+				if (left) left->revert ^= 1;
+				if (right) right->revert ^= 1;
+			}
+			nodeValue = joinValueDelta(nodeValue, delta);
+			subTreeValue = joinValueDelta(subTreeValue, 
+																		_update(delta, size));
+			if (left) left->delta = joinDeltas(left->delta, delta);
+			if (right) right->delta = joinDeltas(right->delta, delta);
+			delta = updateDefault;
+		}
+
+		ll getSubtreeValue() {
+			return joinValueDelta(subTreeValue, _update(delta, size));
+		}
+		
+		void update() {
+			subTreeValue = joinValueDelta(nodeValue, delta);
+			size = 1;
+			if (left) {
+				subTreeValue = _query(subTreeValue,
+															left->getSubtreeValue());
+				size += left->size;
+			}
+			if (right) {
+				subTreeValue = _query(subTreeValue, 
+															right->getSubtreeValue());
+				size += right->size;
+		}}
+	};
+	
+	vector<Node> nodes;
+	
+	LCT(int n) : nodes(n) {
+		for (int i = 0; i < n; i++) nodes[i].id = i;
+	}
+	
+	void connect(Node* ch, Node* p, int isLeftChild) {
+		if (ch) ch->parent = p;
+		if (isLeftChild >= 0) {
+			if (isLeftChild) p->left = ch;
+			else p->right = ch;
+	}}
+
+	void rotate(Node* x) {
+		Node* p = x->parent;
+		Node* g = p->parent;
+		bool isRootP = p->isRoot();
+		bool leftChildX = (x == p->left);
+
+		connect(leftChildX ? x->right : x->left, p, leftChildX);
+		connect(p, x, !leftChildX);
+		connect(x, g, isRootP ? -1 : p == g->left);
+		p->update();
+	}
+	
+	void splay(Node* x) {
+		while (!x->isRoot()) {
+			Node* p = x->parent;
+			Node* g = p->parent;
+			if (!p->isRoot()) g->push();
+			p->push();
+			x->push();
+			if (!p->isRoot()) rotate((x == p->left) == 
+															 (p == g->left) ?  p : x);
+			rotate(x);
+		}
+		x->push();
+		x->update();
+	}
+	
+	Node* expose(Node* x) {
+		Node* last = nullptr;
+		for (Node* y = x; y; y = y->parent) {
+			splay(y);
+			y->left = last;
+			last = y;
+		}
+		splay(x);
+		return last;
+	}
+	
+	void makeRoot(Node* x) {
+		expose(x);
+		x->revert ^= 1;
+	}
+	
+	bool connected(Node* x, Node* y) {
+		if (x == y) return true;
+		expose(x);
+		expose(y);
+		return x->parent;
+	}
+	
+	void link(Node* x, Node* y) {
+		assert(!connected(x, y)); // not yet connected!
+		makeRoot(x);
+		x->parent = y;
+	}
+	
+	void cut(Node* x, Node* y) {
+		makeRoot(x);
+		expose(y);
+		//must be a tree edge!
+		assert(!(y->right != x || x->left != nullptr));
+		y->right->parent = nullptr;
+		y->right = nullptr;
+	}
+
+	Node* lca(Node* x, Node* y) {
+		assert(connected(x, y));
+		expose(x);
+		return expose(y);
+	}
+	
+	ll query(Node* from, Node* to) {
+		makeRoot(from);
+		expose(to);
+		if (to) return to->getSubtreeValue();
+		return queryDefault;
+	}
+	
+	void modify(Node* from, Node* to, ll delta) {
+		makeRoot(from);
+		expose(to);
+		to->delta = joinDeltas(to->delta, delta);
+	}
+};
\ No newline at end of file
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
new file mode 100644
index 0000000..b38b838
--- /dev/null
+++ b/datastructures/RMQ.cpp
@@ -0,0 +1,27 @@
+vector<int> values;
+vector<vector<int>> rmq;
+
+int select(int a, int b) {
+	return values[a] <= values[b] ? a : b;
+}
+
+void build() {
+	for(int i = 0, s = 1, ss = 1; s <= values.size(); ss=s, s*=2, i++) {
+		for(int l = 0; l + s <= values.size(); l++) {
+			if(i == 0) rmq[0][l] = l;
+			else {
+				int r = l + ss;
+				rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]);
+}}}}
+
+void init(vector<int>& v) {
+	values = v;
+	rmq = vector<vector<int>>(floor(log2(values.size()))+1, vector<int>(values.size()));
+	build();
+}
+
+int query(int l, int r) {
+	if(l >= r) return l;
+	int s = floor(log2(r-l)); r = r - (1 << s);
+	return select(rmq[s][l],rmq[s][r]);
+}
\ No newline at end of file
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 1c529a4..8d1cb02 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -1,35 +1,131 @@
 \section{Datenstrukturen}
 
-\subsection{Union-Find}
-\lstinputlisting{datastructures/unionFind.cpp}
+\begin{algorithm}{Union-Find}
+	\begin{methods}
+		\method{init}{legt n einzelne Unions an}{n}
+		\method{findSet}{findet den Repräsentanten}{\log(n)}
+		\method{unionSets}{vereint 2 Mengen}{\log(n)}
+		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
+	\end{methods}
+	\sourcecode{datastructures/unionFind.cpp}
+\end{algorithm}
 
-\subsection{Segmentbaum}
-\lstinputlisting{datastructures/segmentTree.cpp}
+\begin{algorithm}{Segmentbaum}
+	\begin{methods}
+		\method{init}{baut den Baum auf}{n}
+		\method{query}{findet das min(max) in [l, r)}{\log(n)}
+		\method{update}{ändert einen Wert}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/segmentTree.cpp}
+	
+	\subsubsection{Lazy Propagation}
+	Increment modifications, maximum queries
+	\sourcecode{datastructures/lazyPropagation1.cpp}
+	
+	Assignment modifications, sum queries
+	\sourcecode{datastructures/lazyPropagation2.cpp}
+\end{algorithm}
 
-\subsection{2D-Segmentbaum}
-\lstinputlisting{datastructures/segmentTree2D.cpp}
+\begin{algorithm}{Fenwick Tree}
+	\begin{methods}
+		\method{init}{baut den Baum auf}{n\*\log(n)}
+		\method{prefix\_sum}{summe von [0, i]}{\log(n)}
+		\method{update}{addiert ein Delta zu einem Element}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/fenwickTree.cpp}
+	
+	\begin{methods}
+		\method{init}{baut den Baum auf}{n\*\log(n)}
+		\method{prefix\_sum}{summe von [0, i]}{\log(n)}
+		\method{update}{addiert ein Delta zu allen Elementen [l, r)}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/fenwickTree2.cpp}
+\end{algorithm}
 
-\subsection{Fenwick Tree}
-\lstinputlisting{datastructures/fenwickTree.cpp}
-\lstinputlisting{datastructures/fenwickTreeNiklas.cpp}
+\begin{algorithm}{Wavelet Tree}
+	\begin{methods}
+		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
+		\method{kth}{sort$[l, r)[k]$}{\log(n)}
+		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/waveletTree.cpp}
+\end{algorithm}
 
-\subsection{Sparse Table}
-\lstinputlisting{datastructures/sparseTable.cpp}
+\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
+	\begin{methods}
+		\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/firstUnused.cpp}
+\end{algorithm}
 
-\subsection{STL-Tree}
-\lstinputlisting{datastructures/stlTree.cpp}
+\begin{algorithm}{Treap (Cartesian Tree)}
+	\sourcecode{datastructures/treap.cpp}
+\end{algorithm}
 
-\subsection{STL-Rope (Implicit Cartesian Tree)}
-\lstinputlisting{datastructures/stlRope.cpp}
+\begin{algorithm}[optional]{Range Minimum Query}
+	\begin{methods}
+		\method{init}{baut Struktur auf}{n\*\log(n)}
+		\method{query}{Index des Minimums in [l, r)}{1}
+	\end{methods}
+	\sourcecode{datastructures/RMQ.cpp}
+\end{algorithm}
 
-\subsection{Treap (Cartesian Tree)}
-\lstinputlisting{datastructures/treap.cpp}
+\needspace{5\baselineskip}%
+\begin{algorithm}{Range Minimum Query}
+	\begin{methods}
+		\method{init}{baut Struktur auf}{n\*\log(n)}
+		\method{queryIdempotent}{Index des Minimums in [l, r)}{1}
+	\end{methods}
+	\begin{itemize}
+		\item \code{better}-Funktion muss idempotent sein!
+	\end{itemize}
+	\sourcecode{datastructures/sparseTable.cpp}
+\end{algorithm}
 
-\subsection{STL Priority Queue}
-Nicht notwendig, wenn Smaller-Larger-Optimization greift.
-\lstinputlisting{datastructures/stlPQ.cpp}
+\begin{algorithm}{STL-Tree}
+	\sourcecode{datastructures/stlTree.cpp}
+\end{algorithm}
 
-\subsection{Lower/Upper Envelop (Convex Hull Optimization)}
-Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
-\lstinputlisting{datastructures/monotonicConvexHull.cpp}
-\lstinputlisting{datastructures/dynamicConvexHull.cpp}
+\begin{algorithm}{STL HashMap}
+	3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
+	\sourcecode{datastructures/stlHashMap.cpp}
+\end{algorithm}
+
+\begin{algorithm}{STL Priority Queue}
+	Nicht notwendig, wenn Smaller-Larger-Optimization greift.
+	\sourcecode{datastructures/stlPQ.cpp}
+\end{algorithm}
+
+\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
+	\sourcecode{datastructures/stlRope.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
+	Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
+	\sourcecode{datastructures/monotonicConvexHull.cpp}
+	\sourcecode{datastructures/dynamicConvexHull.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Link-Cut-Tree}
+	\begin{methods}
+		\method{Constructor}{baut Wald auf}{n}
+		\method{connected}{prüft ob zwei Knoten im selben baum liegen}{\log(n)}
+		\method{link}{fügt $\{x,y\}$ Kante ein}{\log(n)}
+		\method{cut}{entfernt $\{x,y\}$ Kante}{\log(n)}
+		\method{lca}{berechnet LCA von $x$ und $y$}{\log(n)}
+		\method{query}{berechnet \texttt{query} auf den Knoten des $xy$-Pfades}{\log(n)}
+		\method{modify}{erhöht jeden wert auf dem $xy$-Pfad}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/LCT.cpp}
+\end{algorithm}
+
+\clearpage
+\begin{algorithm}{Persistent}
+	\begin{methods}
+		\method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)}
+		\method{set}{ändert Wert zu Zeitpunkt $t$}{\log(t)}
+		\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
+	\end{methods}
+	\sourcecode{datastructures/persistent.cpp}
+	\sourcecode{datastructures/persistentArray.cpp}
+\end{algorithm}
diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
index 042d26c..18a46d0 100644
--- a/datastructures/dynamicConvexHull.cpp
+++ b/datastructures/dynamicConvexHull.cpp
@@ -1,35 +1,50 @@
 // Upper Envelope, dynamisch.
 struct Line {
-    ll m, b;
-    mutable function<const Line*()> succ;
-    bool operator<(const Line& rhs) const {
-        if (rhs.b != LLONG_MIN) return m < rhs.m;
-        const Line* s = succ();
-        if (!s) return 0;
-        ll x = rhs.m;
-        return b - s->b < (s->m - m) * x;
-    }
+	ll m, b;
+	mutable function<const Line*()> succ;
+	bool operator<(const Line& rhs) const {
+		if (rhs.b != LLONG_MIN) return m < rhs.m;
+		const Line* s = succ();
+		if (!s) return 0;
+		ll x = rhs.m;
+		return b - s->b < (s->m - m) * x;
+	}
 };
+
 struct HullDynamic : public multiset<Line> {
-    bool bad(iterator y) {
-        auto z = next(y);
-        if (y == begin()) {
-            if (z == end()) return 0;
-            return y->m == z->m && y->b <= z->b;
-        }
-        auto x = prev(y);
-        if (z == end()) return y->m == x->m && y->b <= x->b;
-        return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
-    }
-    void insert_line(ll m, ll b) { // Laufzeit: O(log(n))
-        auto y = insert({ m, b });
-        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
-        if (bad(y)) { erase(y); return; }
-        while (next(y) != end() && bad(next(y))) erase(next(y));
-        while (y != begin() && bad(prev(y))) erase(prev(y));
-    }
-    ll query(ll x) { // Laufzeit: O(log(n)) 
-        auto l = *lower_bound((Line) {x, LLONG_MIN});
-        return l.m * x + l.b;
-    }
+	bool bad(iterator y) {
+		auto z = next(y);
+		if (y == begin()) {
+			if (z == end()) return 0;
+			return y->m == z->m && y->b <= z->b;
+		}
+		auto x = prev(y);
+		if (z == end()) return y->m == x->m && y->b <= x->b;
+		return (x->b - y->b)*(z->m - y->m) >=
+					 (y->b - z->b)*(y->m - x->m);
+	}
+
+	// Variant 1: niklasb (2015)
+	void insert_line(ll m, ll b) { // Laufzeit: O(log(n))
+		auto y = insert({m, b});
+		y->succ = [=] {return next(y) == end() ? 0 : &*next(y);};
+		if (bad(y)) {erase(y); return;}
+		while (next(y) != end() && bad(next(y))) erase(next(y));
+		while (y != begin() && bad(prev(y))) erase(prev(y));
+	}
+
+	// Variant 2: barni120400 (2019)
+	void insert_line(ll m, ll b) {
+		auto y = insert({ m, b });
+		if (bad(y)) {erase(y); return;}
+		while (next(y) != end() && bad(next(y))) erase(next(y));
+		y->succ = [=] {return next(y) == end() ? 0 : &*next(y);};
+		while (y != begin() && bad(prev(y))) erase(prev(y));
+		if (y != begin()) prev(y)->succ = [=] {return &*y;};
+	}
+
+	ll query(ll x) { // Laufzeit: O(log(n)) 
+		auto l = *lower_bound((Line) {x, MIN});
+		return l.m * x + l.b;
+	}
 };
diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp
index 86b1138..cac3cf8 100644
--- a/datastructures/fenwickTree.cpp
+++ b/datastructures/fenwickTree.cpp
@@ -1,21 +1,15 @@
-vector<int> FT; // Fenwick-Tree
-int n;
+vector<ll> tree;
 
-// Addiert val zum Element an Index i. O(log(n)).
-void updateFT(int i, int val) {
-	i++; while(i <= n) { FT[i] += val; i += (i & (-i)); }
+void update(int i, ll val) {
+	for (i++; i < sz(tree); i += (i & (-i))) tree[i] += val;
 }
 
-// Baut Baum auf. O(n*log(n)).
-void buildFenwickTree(vector<int>& a) {
-  n = a.size();
-  FT.assign(n+1,0);
-  for(int i = 0; i < n; i++)  updateFT(i,a[i]);
+void init(int n) {
+	tree.assign(n + 1,0);
 }
 
-// Präfix-Summe über das Intervall [0..i]. O(log(n)).
-int prefix_sum(int i) {
-  int sum = 0; i++;
-  while(i > 0) { sum += FT[i]; i -= (i & (-i)); }	
-  return sum;
+ll prefix_sum(int i) {
+	ll sum = 0;
+	for (i++; i > 0; i -= (i & (-i))) sum += tree[i];
+	return sum;
 }
diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp
new file mode 100644
index 0000000..dfd5dc5
--- /dev/null
+++ b/datastructures/fenwickTree2.cpp
@@ -0,0 +1,21 @@
+vector<ll> add, mul;
+
+void update(int l, int r, ll val) {
+	for (int tl = l + 1; tl < sz(add); tl += tl&(-tl))
+		add[tl] += val, mul[tl] -= val * l;
+	for (int tr = r + 1; tr < sz(add); tr += tr&(-tr))
+		add[tr] -= val, mul[tr] += val * r; 
+}
+
+void init(vector<ll>& v) {
+	mul.assign(sz(v) + 1,0);
+	add.assign(sz(v) + 1,0);
+	for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]);
+}
+
+ll prefix_sum (int i) {
+	ll res = 0; i++;
+	for (int ti = i; ti > 0; ti -= ti&(-ti))
+		res += add[ti] * i + mul[ti];
+	return res;
+}
diff --git a/datastructures/fenwickTreeNiklas.cpp b/datastructures/fenwickTreeNiklas.cpp
deleted file mode 100644
index 032f74c..0000000
--- a/datastructures/fenwickTreeNiklas.cpp
+++ /dev/null
@@ -1,56 +0,0 @@
-const int n = 10000; // ALL INDICES START AT 1 WITH THIS CODE!!
-
-// mode 1: update indices, read prefixes
-void update_idx(int tree[], int i, int val) { // v[i] += val
-  for (; i <= n; i += i & -i) tree[i] += val;
-}
-int read_prefix(int tree[], int i) { // get sum v[1..i]
-  int sum = 0;
-  for (; i > 0; i -= i & -i) sum += tree[i];
-  return sum;
-}
-int kth(int k) { // find kth element in tree (1-based index)
-  int ans = 0;
-  for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= n
-    if (ans + (1<<i) <= n && tree[ans + (1<<i)] < k) {
-      ans += 1<<i;
-      k -= tree[ans];
-    }
-  return ans+1;
-}
-
-// mode 2: update prefixes, read indices
-void update_prefix(int tree[], int i, int val) { // v[1..i] += val
-  for (; i > 0; i -= i & -i) tree[i] += val;
-}
-int read_idx(int tree[], int i) { // get v[i]
-  int sum = 0;
-  for (; i <= n; i += i & -i) sum += tree[i];
-  return sum;
-}
-
-// mode 3: range-update range-query
-const int maxn = 100100;
-int n;
-ll mul[maxn], add[maxn];
-
-void update_idx(ll tree[], int x, ll val) {
-  for (int i = x; i <= n; i += i & -i) tree[i] += val;
-}
-void update_prefix(int x, ll val) { // v[x] += val
-  update_idx(mul, 1, val);
-  update_idx(mul, x + 1, -val);
-  update_idx(add, x + 1, x * val);
-}
-ll read_prefix(int x) { // get sum v[1..x]
-  ll a = 0, b = 0;
-  for (int i = x; i > 0; i -= i & -i) a += mul[i], b += add[i];
-  return a * x + b;
-}
-void update_range(int l, int r, ll val) { // v[l..r] += val
-  update_prefix(l - 1, -val);
-  update_prefix(r, val);
-}
-ll read_range(int l, int r) { // get sum v[l..r]
-  return read_prefix(r) - read_prefix(l - 1);
-}
diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp
new file mode 100644
index 0000000..16b0c21
--- /dev/null
+++ b/datastructures/firstUnused.cpp
@@ -0,0 +1,13 @@
+// Erste natürliche Zahl nicht im set used.
+set<int> used;
+int unusedCounter = 1;
+
+int get_first_unused() { // Laufzeit: O(log n) amortisiert.
+	auto it = used.lower_bound(unusedCounter);
+	while (it != used.end() && *it == unusedCounter) {
+		it++;
+		unusedCounter++;
+	}
+	used.insert(unusedCounter);
+	return unusedCounter++;
+}
diff --git a/datastructures/lazyPropagation1.cpp b/datastructures/lazyPropagation1.cpp
new file mode 100644
index 0000000..9fdffb1
--- /dev/null
+++ b/datastructures/lazyPropagation1.cpp
@@ -0,0 +1,47 @@
+int h; // = __lg(2*n)
+//a value that is not used by the update query:
+constexpr ll updateFlag = 0;
+vector<ll> d(N, updateFlag);
+
+void apply(int p, ll value) {
+	tree[p] += value;
+	if (p < tree.size()/2) d[p] += value;
+}
+
+void build(int p) {
+	while (p > 1) {
+		p/=2;
+		tree[p] = max(tree[2*p], tree[2*p+1]) + d[p];
+}}
+
+void push(int p) {
+	for (int s = h; s > 0; --s) {
+		int i = p >> s;
+		if (d[i] != updateFlag) {
+			apply(2*i  , d[i]);
+			apply(2*i+1, d[i]);
+			d[i] = updateFlag;
+}}}
+
+void inc(int l, int r, ll value) {
+	l += sz(tree)/2, r += sz(tree)/2;
+	int l0 = l, r0 = r;
+	for (; l < r; l/=2, r/=2) {
+		if (l&1) apply(l++, value);
+		if (r&1) apply(--r, value);
+	}
+	build(l0); build(r0 - 1);
+}
+
+ll query(int l, int r) {
+	l += sz(tree)/2, r += sz(tree)/2;
+	push(l);
+	push(r - 1);
+	ll res = query_default;
+	for (; l < r; l/=2, r/=2) {
+		if (l&1) res = max(res, tree[l++]);
+		if (r&1) res = max(tree[--r], res);
+	}
+	return res;
+}
+
diff --git a/datastructures/lazyPropagation2.cpp b/datastructures/lazyPropagation2.cpp
new file mode 100644
index 0000000..e90c671
--- /dev/null
+++ b/datastructures/lazyPropagation2.cpp
@@ -0,0 +1,50 @@
+void calc(int p, ll k) {
+	if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1];
+	else tree[p] = d[p] * k;
+}
+
+void apply(int p, ll value, int k) {
+	tree[p] = value * k;
+	if (p < sz(tree)/2) d[p] = value;
+}
+
+void build(int l, int r) {
+	int k = 2;
+	for (l += sz(tree)/2, r += sz(tree)/2-1; l > 1; k <<= 1) {
+		l/=2, r/=2;
+		for (int i = r; i >= l; --i) calc(i, k);
+}}
+
+void push(int l, int r) {
+	int s = h, k = 1 << (h-1);
+	for (l += sz(tree)/2, r += sz(tree)/2-1; s > 0; --s, k/=2) {
+		for (int i = l >> s; i <= r >> s; ++i) {
+			if (d[i] != updateFlag) {
+				apply(2*i  , d[i], k);
+				apply(2*i+1, d[i], k);
+				d[i] = updateFlag;
+}}}}
+
+void modify(int l, int r, ll value) {
+	if (value == updateFlag) return;
+	push(l, l + 1);
+	push(r - 1, r);
+	int l0 = l, r0 = r, k = 1;
+	for (l += sz(tree)/2, r += sz(tree)/2; l<r; l/=2, r/=2, k*=2) {
+		if (l&1) apply(l++, value, k);
+		if (r&1) apply(--r, value, k);
+	}
+	build(l0, l0 + 1);
+	build(r0 - 1, r0);
+}
+
+ll query(int l, int r) {
+	push(l, l + 1);
+	push(r - 1, r);
+	ll res = query_default;
+	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l/=2, r/=2) {
+		if (l&1) res += tree[l++];
+		if (r&1) res += tree[--r];
+	}
+	return res;
+}
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
index 64af841..8035b17 100644
--- a/datastructures/monotonicConvexHull.cpp
+++ b/datastructures/monotonicConvexHull.cpp
@@ -3,21 +3,22 @@
 vector<ll> ms, bs; int ptr = 0;
 
 bool bad(int l1, int l2, int l3) {
-  return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < (bs[l2]-bs[l1])*(ms[l1]-ms[l3]);
+	return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < 
+				 (bs[l2]-bs[l1])*(ms[l1]-ms[l3]);
 }
 
 void add(ll m, ll b) { // Laufzeit O(1) amortisiert
-  ms.push_back(m); bs.push_back(b);
-  while (ms.size() >= 3 && bad(ms.size() - 3, ms.size() - 2, ms.size() - 1)) {
-    ms.erase(ms.end() - 2); bs.erase(bs.end() - 2);
-  }
-  ptr = min(ptr, ms.size() - 1);
+	ms.push_back(m); bs.push_back(b);
+	while (sz(ms) >= 3 && bad(sz(ms)-3, sz(ms)-2, sz(ms)-1)) {
+		ms.erase(ms.end() - 2); bs.erase(bs.end() - 2);
+	}
+	ptr = min(ptr, sz(ms) - 1);
 }
 
-ll get(int idx, ll x) { return ms[idx] * x + bs[idx]; }
+ll get(int idx, ll x) {return ms[idx] * x + bs[idx];}
 
 ll query(ll x) { // Laufzeit: O(1) amortisiert
-  if (ptr >= (int)ms.size()) ptr = ms.size() - 1;
-  while (ptr < (int)ms.size() - 1 && get(ptr + 1, x) < get(ptr, x)) ptr++;
-  return ms[ptr] * x + bs[ptr];
+	if (ptr >= sz(ms)) ptr = sz(ms) - 1;
+	while (ptr < sz(ms)-1 && get(ptr + 1, x) < get(ptr, x)) ptr++;
+	return get(ptr, x);
 }
diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp
new file mode 100644
index 0000000..befecf7
--- /dev/null
+++ b/datastructures/persistent.cpp
@@ -0,0 +1,19 @@
+template<typename T>

+struct persistent {

+	int& time;

+	vector<pair<int, T>> data;

+

+	persistent(int& time, T value = {}) 

+		: time(time), data(1, {time, value}) {}

+	

+	T get(int t) {

+		return prev(upper_bound(all(data), 

+														pair<int, T>(t+1, {})))->second;

+	}

+	

+	int set(T value) {

+		time+=2;

+		data.push_back({time, value});

+		return time;

+	}

+};

diff --git a/datastructures/persistentArray.cpp b/datastructures/persistentArray.cpp
new file mode 100644
index 0000000..665d908
--- /dev/null
+++ b/datastructures/persistentArray.cpp
@@ -0,0 +1,26 @@
+template<typename T>

+struct persistentArray{

+	int time = 0;

+	vector<persistent<T>> data;

+	vector<pair<int, int>> mods;

+

+	persistentArray(int n, T value = {}) 

+		: time(0), data(n, {time, value}) {}

+

+	T get(int p, int t) {

+		return data[p].get(t);

+	}

+

+	int set(int p, T value) {

+		mods.push_back({p, time});

+		return data[p].set(value);

+	}

+

+	void reset(int t) {

+		while (!mods.empty() && mods.back().second > t) {

+			data[mods.back().first].data.pop_back();

+			mods.pop_back();

+		}

+		time = t;

+	}

+};
\ No newline at end of file
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp
index 3905151..09ff694 100644
--- a/datastructures/segmentTree.cpp
+++ b/datastructures/segmentTree.cpp
@@ -1,27 +1,43 @@
-// Laufzeit: init: O(n), query: O(log n), update: O(log n)
-// Berechnet das Maximum im Array.
-int a[MAX_N], m[4 * MAX_N];
+vector<ll> tree;
+constexpr ll query_default = 0;
 
-int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) {
-	if (x <= X && Y <= y) return m[k];
-	if (y < X || Y < x) return -INF; // Ein "neutrales" Element.
-	int M = (X + Y) / 2;
-	return max(query(x, y, 2*k+1, X, M), query(x, y, 2*k+2, M+1, Y));
+ll combine(ll a, ll b) {
+	return a + b;
 }
 
-void update(int i, int v, int k = 0, int X = 0, int Y = MAX_N - 1) {
-	if (i < X || Y < i) return;
-	if (X == Y) { m[k] = v; a[i] = v; return; }
-	int M = (X + Y) / 2;
-	update(i, v, 2 * k + 1, X, M);
-	update(i, v, 2 * k + 2, M + 1, Y);
-	m[k] = max(m[2 * k + 1], m[2 * k + 2]);
+void init(vector<ll>& values) {
+	tree.assign(sz(values)*2, 0);
+	copy(values.begin(), values.end(), tree.begin() + sz(values));
+	for (int i = sz(tree)/2 - 1; i > 0; --i) {
+		tree[i] = combine(tree[2*i], tree[2*i+1]);
+}}
+
+void update(int p, ll value) {
+	for (tree[p += sz(tree)/2] = value, p /= 2; p > 0; p /= 2) {
+		tree[p] = combine(tree[2*p], tree[2*p+1]);
+}}
+
+ll query(int l, int r) {
+	ll resL = query_default;
+	ll resR = query_default;
+	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) {
+		if (l&1) resL = combine(resL, tree[l++]);
+		if (r&1) resR = combine(tree[--r], resR);
+	}
+	return combine(resL, resR);
 }
 
-void init(int k = 0, int X = 0, int Y = MAX_N - 1) {
-	if (X == Y) { m[k] = a[X]; return; }
-	int M = (X + Y) / 2;
-	init(2 * k + 1, X, M);
-	init(2 * k + 2, M + 1, Y);
-	m[k] = max(m[2 * k + 1], m[2 * k + 2]);
+// Oder: Intervall-Modifikation, Punkt-Query:
+void modify(int l, int r, ll value) {
+	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) {
+		if (l&1) {tree[l] = combine(tree[l], value); l++;};
+		if (r&1) {--r; tree[r] = combine(value, tree[r]);};
+}}
+
+ll query(int p) {
+	ll res = query_default;
+	for (p += sz(tree)/2; p > 0; p = p/2) {
+		res = combine(res, tree[p]);
+	}
+	return res;
 }
diff --git a/datastructures/segmentTree2D.cpp b/datastructures/segmentTree2D.cpp
deleted file mode 100644
index a9d129b..0000000
--- a/datastructures/segmentTree2D.cpp
+++ /dev/null
@@ -1,58 +0,0 @@
-// 1-indiziert. Array t: [4*n][4*m]. Nur die _x-Varianten aufrufen.
-// Laufzeit: build: O(n*m), update, sum: O(log(n)*log(m))
-void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
-  if (ly == ry) {
-    if (lx == rx)vt[vx][vy] = a[lx][ly];
-    else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
-  } else {
-    int my = (ly + ry) / 2;
-    build_y(vx, lx, rx, vy*2, ly, my);
-    build_y(vx, lx, rx, vy*2+1, my+1, ry);
-    t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
-}}
- 
-void build_x(int vx = 1, int lx = 0, int rx = N-1) {
-  if (lx != rx) {
-    int mx = (lx + rx) / 2;
-    build_x(vx*2, lx, mx);
-    build_x(vx*2+1, mx+1, rx);
-  }
-  build_y(vx, lx, rx, 1, 0, m-1);
-}
-
-int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
-  if (ly > ry) return 0;
-  if (ly == tly && try_ == ry) return t[vx][vy];
-  int tmy = (tly + try_) / 2;
-  return sum_y(vx, vy*2, tly, tmy, ly, min(ry,tmy))
-    + sum_y(vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
-}
-
-int sum_x(int vx=1, int tlx=0, int trx=n-1,int lx,int rx,int ly,int ry) {
-  if (lx > rx) return 0;
-  if (lx == tlx && trx == rx) return sum_y(vx, 1, 0, m-1, ly, ry);
-  int tmx = (tlx + trx) / 2;
-  return sum_x(vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
-    + sum_x(vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
-}
-
-void update_y(int vx, int lx, int rx, int vy, int ly, int ry,
-    int x, int y, int new_val) {
-  if (ly == ry) {
-    if (lx == rx) t[vx][vy] = new_val;
-    else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
-  } else {
-    int my = (ly + ry) / 2;
-    if (y <= my) update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
-    else update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
-    t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
-}}
- 
-void update_x(int vx=1, int lx=0, int rx=n-1, int x, int y, int new_val) {
-  if (lx != rx) {
-    int mx = (lx + rx) / 2;
-    if (x <= mx) update_x(vx*2, lx, mx, x, y, new_val);
-    else update_x(vx*2+1, mx+1, rx, x, y, new_val);
-  }
-  update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
-}
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
index 52867de..3d11119 100644
--- a/datastructures/sparseTable.cpp
+++ b/datastructures/sparseTable.cpp
@@ -1,27 +1,24 @@
 struct SparseTable {
-  int st[MAX_N][MAX_LOG + 1], log[MAX_N + 1]; // Achtung: 2^MAX_LOG > MAX_N
-  vector<int> *a;
+  vector<vector<int>> st;
+  vector<ll> *a;
 
-  // Funktion muss idempotent sein! Hier Minimum.
-  bool better(int lidx, int ridx) { return a->at(lidx) <= a->at(ridx); }
+  bool better(int lidx, int ridx) {
+    return a->at(lidx) <= a->at(ridx);
+  }
 
-  void init(vector<int> *vec) {
+  void init(vector<ll> *vec) {
     a = vec;
-    for (int i = 0; i < (int)a->size(); i++) st[i][0] = i;
-    for (int j = 1; j <= MAX_LOG; j++) {
-      for (int i = 0; i + (1 << j) <= (int)a->size(); i++) {
-        st[i][j] = better(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])
-            ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
-    }}
+    st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a)));
+    for (int i = 0; i < sz(*a); i++) st[0][i] = i;
+    for (int j = 0; (2 << j) <= sz(*a); j++) {
+      for (int i = 0; i + (2 << j) <= sz(*a); i++) {
+        st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)])
+                            ? st[j][i] : st[j][i + (1 << j)];
+  }}}
 
-    log[1] = 0;
-    for (int i = 2; i <= MAX_N; i++) log[i] = log[i/2] + 1;
-  }
-  
-  // Gibt Index des Ergebnisses in [l,r]. Laufzeit: O(1)
   int queryIdempotent(int l, int r) {
-    int j = log[r - l + 1];
-    return better(st[l][j], st[r - (1 << j) + 1][j])
-        ? st[l][j] : st[r - (1 << j) + 1][j];
+    int j = __lg(r - l); //31 - __builtin_clz(r - l);
+    return better(st[j][l] , st[j][r - (1 << j)])
+                ? st[j][l] : st[j][r - (1 << j)];
   }
-};
+};
\ No newline at end of file
diff --git a/datastructures/stlHashMap.cpp b/datastructures/stlHashMap.cpp
new file mode 100644
index 0000000..b107dde
--- /dev/null
+++ b/datastructures/stlHashMap.cpp
@@ -0,0 +1,17 @@
+#include <ext/pb_ds/assoc_container.hpp>
+using namespace __gnu_pbds;
+
+template<typename T>
+struct betterHash {
+	size_t operator()(T o) const {
+		size_t h = hash<T>()(o) ^ 42394245; //random value
+		h = ((h >> 16) ^ h) * 0x45d9f3b;
+		h = ((h >> 16) ^ h) * 0x45d9f3b;
+		h = ((h >> 16) ^ h);
+		return h;
+}};
+
+template<typename K, typename V, typename H = betterHash<K>>
+using hashMap = gp_hash_table<K, V, H>;
+template<typename K, typename H = betterHash<K>>
+using hashSet = gp_hash_table<K, null_type, H>;
diff --git a/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp
index 1de4abf..b48223b 100644
--- a/datastructures/stlPQ.cpp
+++ b/datastructures/stlPQ.cpp
@@ -1,6 +1,7 @@
 #include <ext/pb_ds/priority_queue.hpp>
 template<typename T>
-using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>; // greater<T> für Min-Queue
+// greater<T> für Min-Queue
+using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>;
 
 int main() {
 	priorityQueue<int> pq;
diff --git a/datastructures/stlRope.cpp b/datastructures/stlRope.cpp
index 9179a60..804cd67 100644
--- a/datastructures/stlRope.cpp
+++ b/datastructures/stlRope.cpp
@@ -5,4 +5,4 @@ v.push_back(num); // O(log(n))
 rope<int> sub = v.substr(start, length); // O(log(n))
 v.erase(start, length); // O(log(n))
 v.insert(v.mutable_begin() + offset, sub); // O(log(n))
-for(auto it = v.mutable_begin(); it != v.mutable_end(); it++) {...}
+for(auto it = v.mutable_begin(); it != v.mutable_end(); it++)
diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp
index 6dde73a..29491c4 100644
--- a/datastructures/stlTree.cpp
+++ b/datastructures/stlTree.cpp
@@ -1,14 +1,16 @@
-#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;
+template<typename T>
+using Tree = tree<T, null_type, less<T>, rb_tree_tag,
+									tree_order_statistics_node_update>;
 
 int main() {
-	Tree X;
-	for (int i = 1; i <= 16; i <<= 1) X.insert(i); // {1, 2, 4, 8, 16}
+	Tree<int> X;
+	// insert {1, 2, 4, 8, 16}
+	for (int i = 1; i <= 16; i *= 2) X.insert(i);
 	cout << *X.find_by_order(3) << endl; // => 8
-	cout << X.order_of_key(10) << endl; // => 4 = min i, mit X[i] >= 10
+	cout << X.order_of_key(10) << endl;
+	// => 4 = min i, mit X[i] >= 10
 	return 0;
 }
diff --git a/datastructures/treap.cpp b/datastructures/treap.cpp
index 4de3328..6296392 100644
--- a/datastructures/treap.cpp
+++ b/datastructures/treap.cpp
@@ -1,39 +1,79 @@
-struct item {
-  int key, prior;
-  item *l, *r;
-  item() {}
-  item(int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) {}
+struct node {
+	int key, prio, left, right, size;
+	node(int key, int prio) : key(key), prio(prio), left(-1), 
+														right(-1), size(1) {};
 };
 
-void split(item *t, int key, item *l, item *r) {
-  if (!t) l = r = NULL;
-  else if (key < t->key) split(t->l, key, l, t->l), r = t;
-  else split(t->r, key, t->r, r), l = t;
-}
+vector<node> treap;
 
-void insert(item *t, item *it) {
-  if (!t) t = it;
-  else if (it->prior > t->prior) split(t, it->key, it->l, it->r), t = it;
-  else insert(it->key < t->key ? t->l : t->r, it);
+int getSize(int root) {
+	return root < 0 ? 0 : treap[root].size;
 }
 
-void merge(item *t, item *l, item *r) {
-  if (!l || !r) t = l ? l : r;
-  else if (l->prior > r->prior) merge(l->r, l->r, r), t = l;
-  else merge(r->l, l, r->l), t = r;
+void update(int root) {
+	if (root < 0) return;
+	treap[root].size = 1 + getSize(treap[root].left)
+											 + getSize(treap[root].right);
 }
 
-void erase(item *t, int key) {
-  if (t->key == key) merge (t, t->l, t->r);
-  else erase(key < t->key ? t->l : t->r, key);
+pair<int, int> split(int root, int minKeyRight) {
+	if (root < 0) return {-1, -1};
+	if (treap[root].key >= minKeyRight) {
+		auto leftSplit = split(treap[root].left, minKeyRight);
+		treap[root].left = leftSplit.second;
+		update(root);
+		leftSplit.second = root;
+		return leftSplit;
+	} else {
+		auto rightSplit = split(treap[root].right, minKeyRight);
+		treap[root].right = rightSplit.first;
+		update(root);
+		rightSplit.first = root;
+		return rightSplit;
+}}
+
+int merge (int left, int right) {
+	if (left < 0) return right;
+	if (right < 0) return left;
+	if (treap[left].prio < treap[right].prio) { //min priority heap
+		treap[left].right = merge(treap[left].right, right);
+		update(left);
+		return left;
+	} else {
+		treap[right].left = merge(left, treap[right].left);
+		update(right);
+		return right;
+}}
+
+//insert values with high priority first
+int insert(int root, int key, int prio) {
+	int next = sz(treap);
+	treap.emplace_back(key, prio);
+	auto t = split(root, key);
+	//returns new root
+	return merge(merge(t.first, next), t.second);
 }
 
-item *unite(item *l, item *r) {
-  if (!l || !r) return l ? l : r;
-  if (l->prior < r->prior) swap(l, r);
-  item * lt, rt;
-  split(r, l->key, lt, rt);
-  l->l = unite(l->l, lt);
-  l->r = unite(l->r, rt);
-  return l;
+int remove(int root, int key) {
+	if (root < 0) return -1;
+	if (key < treap[root].key) {
+		treap[root].left = remove(treap[root].left, key);
+		update(root);
+		return root;
+	} else if (key > treap[root].key) {
+		treap[root].right = remove(treap[root].right, key);
+		update(root);
+		return root;
+	} else { //check prio?
+		return merge(treap[root].left, treap[root].right);
+}}
+
+int kth(int root, int k) {
+	if (root < 0) return -1;
+	int leftSize = getSize(treap[root].left);
+	if (k < leftSize) return kth(treap[root].left, k);
+	else if (k > leftSize) {
+		return kth(treap[root].right, k - 1 - leftSize);
+	}
+	return root;
 }
diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
index 99b19fc..03ff63e 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -1,21 +1,22 @@
-// Laufzeit: O(n*alpha(n))
-// "height" ist obere Schranke für die Höhe der Bäume. Sobald
-// Pfadkompression angewendet wurde, ist die genaue Höhe nicht mehr
-// effizient berechenbar.
-vector<int> parent; // Initialisiere mit Index im Array.
-vector<int> height; // Initialisiere mit 0.
+// unions[i] >= 0 => unions[i] =  parent
+// unions[i]  < 0 => unions[i] = -height
+vector<int> unions;
+
+void init(int n) { //Initialisieren
+	unions.assign(n, -1);
+}
 
 int findSet(int n) { // Pfadkompression
-	if (parent[n] != n) parent[n] = findSet(parent[n]);
-	return parent[n];
+	if (unions[n] < 0) return n;
+	return unions[n] = findSet(unions[n]);
 }
 
 void linkSets(int a, int b) { // Union by rank.
-	if (height[a] < height[b]) parent[a] = b;
-	else if (height[b] < height[a]) parent[b] = a;
+	if (unions[a] > unions[b]) unions[a] = b;
+	else if (unions[b] > unions[a]) unions[b] = a;
 	else {
-		parent[a] = b;
-		height[b]++;
+		unions[a] = b;
+		unions[b]--;
 }}
 
 void unionSets(int a, int b) { // Diese Funktion aufrufen.
diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp
new file mode 100644
index 0000000..225ecee
--- /dev/null
+++ b/datastructures/unionFind2.cpp
@@ -0,0 +1,27 @@
+vector<int> uf;
+
+init(int N) {
+	uf.assign(N,-1); //-1 indicates that every subset has size 1
+}
+
+int findSet(int i) {
+	if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root
+	uf[i] = findSet(uf[i]); //Path-Compression
+	return uf[i];
+}
+	
+void linkSets(int i, int j) {
+	//Take |uf[i]|, where i must be a root, to get the size 
+	//of the subset
+	if(abs(uf[i]) < abs(uf[j])) { //Union-by-size.
+		uf[j] += uf[i]; uf[i] = j; 
+	} else {
+		uf[i] += uf[j]; uf[j] = i; 
+	}
+}
+	
+void unionSets(int i, int j) {
+	if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j));
+} 
+	
+	
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp
new file mode 100644
index 0000000..feef2d4
--- /dev/null
+++ b/datastructures/waveletTree.cpp
@@ -0,0 +1,48 @@
+struct WaveletTree {

+	using it = vector<ll>::iterator;

+	WaveletTree *ln, *rn;

+	ll lo, hi;

+	vector<int> b;

+

+private:

+	WaveletTree(it from, it to, ll x, ll y)

+	: ln(nullptr), rn(nullptr), lo(x), hi(y), b(1) {

+		ll mid = (lo + hi) / 2;

+		auto f = [&](ll x){return x < mid;};

+		for (it c = from; c != to; c++) {

+			b.push_back(b.back() + f(*c));

+		}

+		if (lo + 1 >= hi || from == to) return;

+		it pivot = stable_partition(from, to, f);

+		ln = new WaveletTree(from, pivot, lo, mid);

+		rn = new WaveletTree(pivot, to, mid, hi);

+	}

+

+public:

+	WaveletTree(vector<ll> in) : WaveletTree(all(in), 

+		*min_element(all(in)), *max_element(all(in)) + 1){}

+

+	// kth element in sort[l, r) all 0-indexed

+	ll kth(int l, int r, int k) {

+		if (l >= r || k >= r - l) return -1;

+		if (lo + 1 >= hi) return lo;

+		int inLeft = b[r] - b[l];

+		if (k < inLeft) {

+			return ln->kth(b[l], b[r], k);

+		} else {

+			return rn->kth(l-b[l], r-b[r], k-inLeft);

+	}}

+

+	// count elements in[l, r) smaller than k

+	int countSmaller(int l, int r, ll k) {

+		if (l >= r || k <= lo) return 0;

+		if (hi <= k) return r - l;

+		return ln->countSmaller(b[l], b[r], k) + 

+					 rn->countSmaller(l-b[l], r-b[r], k);

+	}

+

+	~WaveletTree(){

+		delete ln;

+		delete rn;

+	}

+};