19 files changed, 214 insertions, 229 deletions
diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index c9f3d2a..38d63d9 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -10,7 +10,7 @@
 	
 	\subsubsection{Lazy Propagation}
 	Assignment modifications, sum queries \\
-	\method{lower\_bound}{erster Index in $[l, r)$ $\geq$ x (erfordert max-combine)}{\log(n)}
+	\method{binary\_search}{kleinstes $x$ in $[l, r]$ mit $f(\text{query}(l, x))$ (monoton in $x$)}{\log(n)}
 	\sourcecode{datastructures/lazyPropagation.cpp}
 \end{algorithm}
 
@@ -20,6 +20,8 @@
 		\method{kth}{sort $[l, r)[k]$}{\log(\Sigma)}
 		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)}
 	\end{methods}
+	$\Sigma$ ist die Gr\"o\ss e des Eingabebereichs, d.h.
+	$\mathit{max} - \mathit{min}$.
 	\sourcecode{datastructures/waveletTree.cpp}
 \end{algorithm}
 \columnbreak
@@ -27,15 +29,15 @@
 \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{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)$. $l\leq r$!}{\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}
@@ -56,7 +58,7 @@
 \begin{algorithm}{Range Minimum Query}
 	\begin{methods}
 		\method{init}{baut Struktur auf}{n\*\log(n)}
-		\method{queryIdempotent}{Index des Minimums in $[l, r)$. $l<r$!}{1}
+		\method{query}{Index des Minimums in $[l, r)$}{1}
 	\end{methods}
 	\begin{itemize}
 		\item \code{better}-Funktion muss idempotent sein!
@@ -64,11 +66,19 @@
 	\sourcecode{datastructures/sparseTable.cpp}
 \end{algorithm}
 
+\begin{algorithm}[optional]{Range Aggregate Query}
+	\begin{methods}
+		\method{init}{baut Struktur auf}{n\*\log(n)}
+		\method{query}{Aggregat über $[l,r)$}{1}
+	\end{methods}
+	\sourcecode{datastructures/sparseTableDisjoint.cpp}
+\end{algorithm}
+
 \begin{algorithm}{STL-Bitset}
 	\sourcecode{datastructures/bitset.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Link-Cut-Tree}
+\begin{algorithm}{Link/Cut Tree}
 	\begin{methods}
 		\method{LCT}{baut Wald auf}{n}
 		\method{connected}{prüft ob zwei Knoten im selben Baum liegen}{\log(n)}
@@ -80,31 +90,45 @@
 	\end{methods}
 	\sourcecode{datastructures/LCT.cpp}
 \end{algorithm}
-\clearpage
+\columnbreak
 
-\begin{algorithm}{Lichao}
-    \sourcecode{datastructures/lichao.cpp}
+\begin{algorithm}{Lower 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.
+	\subsubsection{Monotonic}
+	\begin{methods}
+		\method{add}{add line $mx + b$, $m$ is decreasing}{1}
+		\method{query}{minimum value at $x$, $x$ is increasing}{1}
+	\end{methods}
+	\sourcecode{datastructures/monotonicConvexHull.cpp}
+	\subsubsection{Dynamic}
+	\begin{methods}
+		\method{add}{add line $mx + b$}{\log(n)}
+		\method{query}{minimum value at $x$}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/dynamicConvexHull.cpp}
+	\subsubsection{Li Chao Tree}
+	Every pair of functions has at most one intersection.
+
+	\begin{methods}
+		\method{insert}{add function}{\log(|xs|)}
+		\method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)}
+	\end{methods}
+	\sourcecode{datastructures/lichao.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Policy Based Data Structures}
-    \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}!
-	\sourcecode{datastructures/stlPriorityQueue.cpp}
-	\columnbreak
 	\sourcecode{datastructures/pbds.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}{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)}
+		\method{UnionFind}{legt $n$ einzelne Elemente an}{n}
+		\method{find}{findet den Repräsentanten}{\log(n)}
+		\method{link}{vereint 2 Mengen}{\log(n)}
+		\method{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)}
+		\method{add}{fügt neues einzelnes Element ein}{1}
+		\method{m\*find + n\*link}{Folge von Befehlen}{n+m\*\alpha(n)}
 	\end{methods}
 	\sourcecode{datastructures/unionFind.cpp}
 \end{algorithm}
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 63e0e13..3e4020e 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,16 +1,16 @@
 struct Line {
 	mutable ll m, c, p;
-	bool operator<(const Line& o) const {return m < o.m;}
-	bool operator<(ll x) const {return p < x;}
+	bool operator<(const Line& o) const { return m > o.m; }
+	bool operator<(ll x) const { return p < x; }
 };
 
-struct HullDynamic : multiset<Line, less<>> { // max über Geraden
+struct HullDynamic : multiset<Line, less<>> { // min über Geraden
 	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
-	ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);}
+	ll div(ll a, ll c) { return a / c - ((a ^ c) < 0 && a % c); }
 
 	bool isect(iterator x, iterator y) {
-		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		if (y == end()) { x->p = INF; return false; }
+		if (x->m == y->m) x->p = x->c < y->c ? INF : -INF;
 		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
@@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
-			x--;
-			if (isect(x, next(x))) {
-				erase(next(x));
-				isect(x, next(x));
-		}}
+			--x;
+			while (isect(x, next(x))) erase(next(x));
+		}
 		while (x != begin() && prev(x)->p >= x->p) {
-			x--;
+			--x;
 			isect(x, erase(next(x)));
 	}}
 
diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp
index eb5cd73..7013613 100644
--- a/content/datastructures/fenwickTree.cpp
+++ b/content/datastructures/fenwickTree.cpp
@@ -1,7 +1,7 @@
 vector<ll> tree;
 
 void update(int i, ll val) {
-	for (i++; i < sz(tree); i += i & -i) tree[i] += val;
+	for (i++; i < ssize(tree); i += i & -i) tree[i] += val;
 }
 
 void init(int n) {
@@ -10,6 +10,6 @@ void init(int n) {
 
 ll prefix_sum(int i) {
 	ll sum = 0;
-	for (i++; i > 0; i -= i & -i) sum += tree[i];
+	for (; i > 0; i &= i-1) sum += tree[i];
 	return sum;
 }
diff --git a/content/datastructures/fenwickTree2.cpp b/content/datastructures/fenwickTree2.cpp
index 9384e3c..7fcdbb9 100644
--- a/content/datastructures/fenwickTree2.cpp
+++ b/content/datastructures/fenwickTree2.cpp
@@ -1,21 +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)
+	for (int tl = l + 1; tl < ssize(add); tl += tl & -tl)
 		add[tl] += val, mul[tl] -= val * l;
-	for (int tr = r + 1; tr < sz(add); tr += tr & -tr)
+	for (int tr = r + 1; tr < ssize(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]);
+void init(vector<ll> &v) {
+	mul.assign(size(v) + 1, 0);
+	add.assign(size(v) + 1, 0);
+	for(int i = 0; i < ssize(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)
+	ll res = 0;
+	for (int ti = i; ti > 0; ti &= ti-1)
 		res += add[ti] * i + mul[ti];
 	return res;
 }
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp
index ab91364..a5be822 100644
--- a/content/datastructures/lazyPropagation.cpp
+++ b/content/datastructures/lazyPropagation.cpp
@@ -1,23 +1,22 @@
 struct SegTree {
 	using T = ll; using U = ll;
-	int n;
 	static constexpr T E = 0; // Neutral element for combine
-	static constexpr U UF = INF; // Unused value by updates
-	vector<T> tree;
+	static constexpr U UF = 1e18; // Unused value by updates
+	int n;
+	vector<T> tree; vector<U> lazy;
 	int h;
-	vector<U> lazy;
-	vector<int> k; // size of segments (optional)
+	vector<ll> k; // size of segments (optional)
 
-	SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E),
+	SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n, E),
 	//SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def),
-			h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) {
-		copy(all(a), tree.begin() + n);
+			lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) {
+		ranges::copy(a, tree.begin() + n);
 		for (int i = n - 1; i > 0; i--) {
 			k[i] = 2 * k[2 * i];
 			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
 	}}
 
-	T comb(T a, T b) {return a + b;} // Modify this + E
+	T comb(T a, T b) { return a + b; } // Modify this + E
 
 	void apply(int i, U val) { // And this + UF
 		tree[i] = val * k[i];
@@ -44,17 +43,17 @@ struct SegTree {
 	void update(int l, int r, U val) {
 		l += n, r += n;
 		int l0 = l, r0 = r;
-		push(l0), push(r0 - 1);
+		push(l0), push(r0);
 		for (; l < r; l /= 2, r /= 2) {
 			if (l&1) apply(l++, val);
 			if (r&1) apply(--r, val);
 		}
-		build(l0), build(r0 - 1);
+		build(l0), build(r0);
 	}
 
 	T query(int l, int r) {
 		l += n, r += n;
-		push(l), push(r - 1);
+		push(l), push(r);
 		T resL = E, resR = E;
 		for (; l < r; l /= 2, r /= 2) {
 			if (l&1) resL = comb(resL, tree[l++]);
@@ -64,21 +63,23 @@ struct SegTree {
 	}
 
 	// Optional:
-	int lower_bound(int l, int r, T x) {
+	int binary_search(int l, int r, auto &&f) {
+		if (f(E)) return l;
 		l += n, r += n;
-		push(l), push(r - 1);
+		push(l), push(r);
 		int a[64] = {}, lp = 0, rp = 64;
 		for (; l < r; l /= 2, r /= 2) {
 			if (l&1) a[lp++] = l++;
 			if (r&1) a[--rp] = --r;
 		}
-		for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this
+		T x = E, y = x;
+		for (int i : a) if (i != 0 && f(x = comb(y = x, tree[i]))) {
 			while (i < n) {
 				push_down(i);
-				if (tree[2 * i] >= x) i = 2 * i; // And this
-				else i = 2 * i + 1;
+				if (f(x = comb(y, tree[2*i]))) i = 2 * i;
+				else i = 2 * i + 1, y = x;
 			}
-			return i - n;
+			return i - n + 1;
 		}
 		return -1;
 	}
diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index 9c41934..da965dd 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -1,9 +1,10 @@
 vector<ll> xs; // IMPORTANT: Initialize before constructing!
-int findX(ll i) {return lower_bound(all(xs), i) - begin(xs);}
+int findX(ll i) {
+	return ranges::lower_bound(xs, i) - begin(xs); }
 
-struct Fun { // Default: Linear function. Change as needed. 
+struct Fun { // Default: Linear function. Change as needed.
 	ll m, c;
-	ll operator()(int x) {return m*xs[x] + c;}
+	ll operator()(int x) { return m*xs[x] + c; }
 };
 
 // Default: Computes min. Change lines with comment for max.
@@ -11,18 +12,18 @@ struct Lichao {
 	static constexpr Fun id = {0, INF}; // {0, -INF}
 	int n, cap;
 	vector<Fun> seg;
-	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
-	
+	Lichao() : n(ssize(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
+
 	void _insert(Fun f, int l, int r, int i) {
 		while (i < 2 * cap) {
 			int m = (l+r)/2;
-			if (m >= n) {r = m; i = 2*i; continue;}
+			if (m >= n) { r = m; i = 2*i; continue; }
 			Fun &g = seg[i];
 			if (f(m) < g(m)) swap(f, g); // >
 			if (f(l) < g(l)) r = m, i = 2*i; // >
 			else l = m, i = 2*i+1;
 	}}
-	void insert(Fun f) {_insert(f, 0, cap, 1);}
+	void insert(Fun f) { _insert(f, 0, cap, 1); }
 
 	void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
 		if (l <= a && b <= r) _insert(f, a, b, i);
@@ -42,5 +43,5 @@ struct Lichao {
 		}
 		return ans;
 	}
-	ll query(ll x) {return _query(findX(x));}
+	ll query(ll x) { return _query(findX(x)); }
 };
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index f1721ae..295acc4 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,25 @@
-// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
-// Gerade hat kleineres pair(m, c) als alle vorherigen.
-struct Line {
-	ll m, c;
-	ll operator()(ll x) {return m*x+c;}
-};
+struct Envelope {
+	struct Line {
+		ll m, b;
+		ll operator()(ll x) { return m*x+b; }
+	};
 
-vector<Line> ls;
-ll ptr = 0;
+	vector<Line> ls;
+	int ptr = 0;
 
-bool bad(Line l1, Line l2, Line l3) {
-	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
-}
+	static bool bad(Line l1, Line l2, Line l3) {
+		return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
+	}
 
-void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
-		ls.pop_back();
+	void add(ll m, ll b) {
+		while (ssize(ls) > 1
+		  && bad(ls.end()[-2], ls.back(), {m,b})) ls.pop_back();
+		ls.push_back({m, b});
+		ptr = min(ptr, (int)ssize(ls) - 1);
 	}
-	ls.push_back({m, c});
-	ptr = min(ptr, sz(ls) - 1);
-}
 
-ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert
-	ptr = min(ptr, sz(ls) - 1);
-	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
-	return ls[ptr](x);
-}
-\ No newline at end of file
+	ll query(ll x) {
+		while (ptr < ssize(ls)-1 && ls[ptr+1](x) < ls[ptr](x)) ptr++;
+		return ls[ptr](x);
+	}
+};
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index de0ace6..734bf91 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -1,14 +1,22 @@
+#include <ext/pb_ds/priority_queue.hpp>
+template<typename T>
+using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
+auto it = pq.push(5); // O(1)
+pq.modify(it, 6);     // O(log n)
+pq.erase(it);         // O(log n)
+pq.join(pq2);         // O(1)
+pq.swap(pq2);         // O(1)
+
 #include <ext/pb_ds/assoc_container.hpp>
 using namespace __gnu_pbds;
 template<typename T>
 using Tree = tree<T, null_type, less<T>, rb_tree_tag,
                   tree_order_statistics_node_update>;
-// T.order_of_key(x): number of elements strictly less than x
-// *T.find_by_order(k): k-th element
+T.order_of_key(x); // number of elements strictly less than x
+auto it = T.find_by_order(k); // k-th element
 
 constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
-template<typename T>
-struct chash {
+template<typename T> struct chash {
 	size_t operator()(T o) const {
 		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index f26680d..ed2f891 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -1,18 +1,18 @@
-template<typename T>
-struct persistent {
-	int& time;
-	vector<pair<int, T>> data;
-
-	persistent(int& time, T value = {}) 
-		: time(time), data(1, {2*time, value}) {}
-	
-	T get(int t) {
-		return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;
-	}
-	
-	int set(T value) {
-		time++;
-		data.push_back({2*time, value});
-		return time;
-	}
-};
+template<typename T>
+struct persistent {
+	int& time;
+	vector<pair<int, T>> data;
+
+	persistent(int& time, T value = {})
+		: time(time), data(1, {2*time, value}) {}
+
+	T get(int t) {
+		return ranges::upper_bound(data,pair{2*t+1, T{}})[-1].second;
+	}
+
+	int set(T value) {
+		time++;
+		data.push_back({2*time, value});
+		return time;
+	}
+};
diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp
index 8326700..903bd0e 100644
--- a/content/datastructures/persistentArray.cpp
+++ b/content/datastructures/persistentArray.cpp
@@ -1,24 +1,24 @@
-template<typename T>
-struct persistentArray {
-	int time;
-	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, data[p].set(value)});
-		return mods.back().second;
-	}
-
-	void reset(int t) {
-		while (!mods.empty() && mods.back().second > t) {
-			data[mods.back().first].data.pop_back();
-			mods.pop_back();
-		}
-		time = t;
-	}
-};
+template<typename T>
+struct persistentArray {
+	int time;
+	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, data[p].set(value)});
+		return mods.back().second;
+	}
+
+	void reset(int t) {
+		while (!mods.empty() && mods.back().second > t) {
+			data[mods.back().first].data.pop_back();
+			mods.pop_back();
+		}
+		time = t;
+	}
+};
diff --git a/content/datastructures/segmentTree.cpp b/content/datastructures/segmentTree.cpp
index 6b69d0b..1fbf886 100644
--- a/content/datastructures/segmentTree.cpp
+++ b/content/datastructures/segmentTree.cpp
@@ -4,14 +4,15 @@ struct SegTree {
 	vector<T> tree;
 	static constexpr T E = 0; // Neutral element for combine
 
-	SegTree(vector<T>& a) : n(sz(a)), tree(2 * n) {
-	//SegTree(int size, T val = E) : n(size), tree(2 * n, val) {
-		copy(all(a), tree.begin() + n);
+	SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) {
+		ranges::copy(a, tree.begin() + n);
+	//SegTree(int size, T val = E) : n(size), tree(2 * n, E) {
+	//	fill(tree.begin() + n, tree.end(), val);
 		for (int i = n - 1; i > 0; i--) { // remove for range update
 			tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
 	}}
 
-	T comb(T a, T b) {return a + b;} // modify this + neutral
+	T comb(T a, T b) { return a + b; } // modify this + neutral
 
 	void update(int i, T val) {
 		tree[i += n] = val; // apply update code
diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp
index b3f946e..5455ef5 100644
--- a/content/datastructures/sparseTable.cpp
+++ b/content/datastructures/sparseTable.cpp
@@ -6,17 +6,17 @@ struct SparseTable {
 		return a[lidx] <= a[ridx] ? lidx : ridx;
 	}
 
-	void init(vector<ll>* vec) {
-		int n = sz(*vec);
-		a = vec->data();
+	void init(vector<ll> &vec) {
+		int n = ssize(vec);
+		a = vec.data();
 		st.assign(__lg(n) + 1, vector<int>(n));
-		iota(all(st[0]), 0);
+		iota(begin(st[0]), end(st[0]), 0);
 		for (int j = 0; (2 << j) <= n; j++) {
 			for (int i = 0; i + (2 << j) <= n; i++) {
 				st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]);
 	}}}
 
-	int queryIdempotent(int l, int r) {
+	int query(int l, int r) {
 		if (r <= l) return -1;
 		int j = __lg(r - l); //31 - builtin_clz(r - l);
 		return better(st[j][l] , st[j][r - (1 << j)]);
diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp
index 55165d4..bcf6b2e 100644
--- a/content/datastructures/sparseTableDisjoint.cpp
+++ b/content/datastructures/sparseTableDisjoint.cpp
@@ -7,16 +7,16 @@ struct DisjointST {
 		return x + y;
 	}
 
-	void init(vector<ll>* vec) {
-		int n = sz(*vec);
-		a = vec->data();
+	void init(vector<ll> &vec) {
+		int n = ssize(vec);
+		a = vec.data();
 		dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral));
 		for (int h = 0, l = 1; l <= n; h++, l *= 2) {
 			for (int c = l; c < n + l; c += 2 * l) {
 				for (int i = c; i < min(n, c + l); i++)
-					dst[h][i + 1] = combine(dst[h][i], vec->at(i));
+					dst[h][i + 1] = combine(dst[h][i], vec[i]);
 				for (int i = min(n, c); i > c - l; i--)
-					dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]);
+					dst[h][i - 1] = combine(vec[i - 1], dst[h][i]);
 	}}}
 
 	ll query(int l, int r) {
diff --git a/content/datastructures/stlHashMap.cpp b/content/datastructures/stlHashMap.cpp
deleted file mode 100644
index b107dde..0000000
--- a/content/datastructures/stlHashMap.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-#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/content/datastructures/stlPriorityQueue.cpp b/content/datastructures/stlPriorityQueue.cpp
deleted file mode 100644
index 32b2455..0000000
--- a/content/datastructures/stlPriorityQueue.cpp
+++ /dev/null
@@ -1,8 +0,0 @@
-#include <ext/pb_ds/priority_queue.hpp>
-template<typename T>
-using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
-
-auto it = pq.push(5);
-pq.modify(it, 6);
-pq.join(pq2);
-// push, join are O(1), pop, modify, erase O(log n) amortized
diff --git a/content/datastructures/stlTree.cpp b/content/datastructures/stlTree.cpp
deleted file mode 100644
index fbb68b9..0000000
--- a/content/datastructures/stlTree.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-#include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
-using namespace std; using namespace __gnu_pbds;
-template<typename T>
-using Tree = tree<T, null_type, less<T>, rb_tree_tag,
-                  tree_order_statistics_node_update>;
-
-int main() {
-	Tree<int> X;
-	for (int i : {1, 2, 4, 8, 16}) X.insert(i);
-	*X.find_by_order(3); // => 8
-	X.order_of_key(10);  // => 4 = min i, mit X[i] >= 10
-}
diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c5a60e9..bddfdb4 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -66,7 +66,7 @@ struct Treap {
 	void insert(int i, ll val) { // and i = val
 		auto [left, right] = split(root, i);
 		treap.emplace_back(val);
-		left = merge(left, sz(treap) - 1);
+		left = merge(left, ssize(treap) - 1);
 		root = merge(left, right);
 	}
 
diff --git a/content/datastructures/unionFind.cpp b/content/datastructures/unionFind.cpp
index dd5a569..8861790 100644
--- a/content/datastructures/unionFind.cpp
+++ b/content/datastructures/unionFind.cpp
@@ -1,26 +1,26 @@
-// unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -size
-vector<int> unions;
+struct UnionFind {
+	vector<int> unions; // unions[i] = parent or unions[i] = -size
 
-void init(int n) { //Initialisieren
-	unions.assign(n, -1);
-}
+	UnionFind(int n): unions(n, -1) {}
 
-int findSet(int a) { // Pfadkompression
-	if (unions[a] < 0) return a;
-	return unions[a] = findSet(unions[a]);
-}
+	int find(int a) {
+		return unions[a] < 0 ? a : unions[a] = find(unions[a]);
+	}
 
-void linkSets(int a, int b) { // Union by size.
-	if (unions[b] > unions[a]) swap(a, b);
-	unions[b] += unions[a];
-	unions[a] = b;
-}
+	bool link(int a, int b) {
+		if ((a = find(a)) == (b = find(b))) return false;
+		if (unions[b] > unions[a]) swap(a, b);
+		unions[b] += unions[a];
+		unions[a] = b;
+		return true;
+	}
 
-void unionSets(int a, int b) { // Diese Funktion aufrufen.
-	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
-}
+	int size(int a) { // optional
+		return -unions[find(a)];
+	}
 
-int size(int a) {
-	return -unions[findSet(a)];
-}
+	int add() { // optional
+		unions.push_back(-1);
+		return ssize(unions) - 1;
+	}
+};
diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp
index 090cdb2..55167b6 100644
--- a/content/datastructures/waveletTree.cpp
+++ b/content/datastructures/waveletTree.cpp
@@ -1,25 +1,20 @@
 struct WaveletTree {
-	using it = vector<ll>::iterator;
-	WaveletTree *ln = nullptr, *rn = nullptr;
+	unique_ptr<WaveletTree> ln, rn;
 	vector<int> b = {0};
 	ll lo, hi;
 
-	WaveletTree(vector<ll> in) : WaveletTree(all(in)) {}
-
-	WaveletTree(it from, it to) : // call above one
-		lo(*min_element(from, to)), hi(*max_element(from, to) + 1) {
+	WaveletTree(auto in) : lo(*ranges::min_element(in)),
+	                       hi(*ranges::max_element(in) + 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));
-		}
+		auto f = [&](ll x) { return x < mid; };
+		for (ll x: in) b.push_back(b.back() + f(x));
 		if (lo + 1 >= hi) return;
-		it pivot = stable_partition(from, to, f);
-		ln = new WaveletTree(from, pivot);
-		rn = new WaveletTree(pivot, to);
+		auto right = ranges::stable_partition(in, f);
+		ln = make_unique<WaveletTree>(
+		  ranges::subrange(begin(in), begin(right)));
+		rn = make_unique<WaveletTree>(right);
 	}
 
-	// kth element in sort[l, r) all 0-indexed
 	ll kth(int l, int r, int k) {
 		if (k < 0 || l + k >= r) return -1;
 		if (lo + 1 >= hi) return lo;
@@ -28,13 +23,10 @@ struct WaveletTree {
 		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;}
 };