too many changes for one commit

- simplify envelope code
- add more files as optional
- allow compiling optional without editing tcr.tex
- formatting changes

5 files changed, 107 insertions, 48 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 37a1dc2..0285490 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -29,7 +29,7 @@
 	\end{methods}
 	\sourcecode{datastructures/fenwickTree2.cpp}
 \end{algorithm}
-\clearpage
+\columnbreak
 
 \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
 	\sourcecode{datastructures/stlRope.cpp}
@@ -54,6 +54,14 @@
 	\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}{Wavelet Tree}
 	\begin{methods}
 		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
@@ -79,7 +87,7 @@
 	\end{methods}
 	\sourcecode{datastructures/LCT.cpp}
 \end{algorithm}
-\clearpage
+\columnbreak
 
 \begin{algorithm}{Union-Find}
 	\begin{methods}
@@ -91,11 +99,37 @@
 	\sourcecode{datastructures/unionFind.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.
+\begin{algorithm}[optional]{Union-Find with size}
+	\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{getSize}{zählt Elemente in Menge, die $i$ enthält}{\log(n)}
+		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
+	\end{methods}
+	\sourcecode{datastructures/unionFind2.cpp}
+\end{algorithm}
+
+\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}
 	\columnbreak
+	\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}
+	\optional{
+		\subsubsection{Li Chao tree \opthint}
+		\sourcecode{datastructures/lichao.cpp}
+	}
 \end{algorithm}
 
 \begin{algorithm}{Persistent}
@@ -105,6 +139,7 @@
 		\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
 	\end{methods}
 	\sourcecode{datastructures/persistent.cpp}
+	\columnbreak
 	\sourcecode{datastructures/persistentArray.cpp}
 \end{algorithm}
 
diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
index d669847..2bd67a6 100644
--- a/datastructures/dynamicConvexHull.cpp
+++ b/datastructures/dynamicConvexHull.cpp
@@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> {
 		auto x = insert({m, b, 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/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
index 44bff83..e7b9b3e 100644
--- a/datastructures/monotonicConvexHull.cpp
+++ b/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,26 @@
-// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
-// Gerade hat kleinere Steigung als alle vorherigen.
-struct Line {
-	ll m, b;
-	ll operator()(ll x) {return m*x+b;}
-};
+struct Envelope {
+	struct Line {
+		ll m, b;
+		ll operator()(ll x) { return m*x+b; }
+	};
 
-vector<Line> ls;
-int ptr = 0;
+	vector<Line> ls;
+	int ptr = 0;
 
-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);
-}
+	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 b) { // Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
-		ls.pop_back();
+	void add(ll m, ll b) {
+		while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) {
+			ls.pop_back();
+		}
+		ls.push_back({m, b});
+		ptr = min(ptr, sz(ls) - 1);
 	}
-	ls.push_back({m, b});
-	ptr = min(ptr, sz(ls) - 1);
-}
 
-ll query(ll x) { // Laufzeit: O(1) amortisiert
-	ptr = min(ptr, sz(ls) - 1);
-	while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
-	return ls[ptr](x);
-}
\ No newline at end of file
+	ll query(ll x) {
+		while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+		return ls[ptr](x);
+	}
+};
diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
new file mode 100644
index 0000000..62ea4cd
--- /dev/null
+++ b/datastructures/test/monotonicConvexHull.cpp
@@ -0,0 +1,26 @@
+#include "../monotonicConvexHull.cpp"
+
+int main() {
+	{
+		Envelope env;
+		env.add(10, 0);
+		assert(env.query(0) == 0);
+		assert(env.query(1) == 10);
+		env.add(8, 5);
+		assert(env.query(1) == 10);
+		assert(env.query(2) == 20);
+		assert(env.query(3) == 29);
+		env.add(7, 10);
+		assert(env.query(10) == 80);
+		env.add(0, 0);
+		assert(env.query(11) == 0);
+	}
+
+	{
+		Envelope env;
+		env.add(1, 0);
+		env.add(0, 10);
+		env.add(-1, 10);
+		assert(env.query(7) == 3);
+	}
+}
diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp
index 5362c4d..d1b9162 100644
--- a/datastructures/unionFind2.cpp
+++ b/datastructures/unionFind2.cpp
@@ -1,25 +1,26 @@
-vector<int> uf;
+// unions[i] >= 0 => unions[i] =  parent
+// unions[i]  < 0 => unions[i] = -size
+vector<int> unions;
 
-init(int N) {
-	uf.assign(N,-1); //-1 indicates that every subset has size 1
+init(int n) {
+	unions.assign(n, -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];
+	if (unions[i] < 0) return i;
+	return unions[i] = findSet(unions[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 linkSets(int a, int b) { // Union by size.
+	if (unions[b] > unions[a]) swap(a, b);
+	unions[b] += unions[a];
+	unions[a] = b;
 }
 
-void unionSets(int i, int j) {
-	if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j));
+void unionSets(int a, int b) {
+	if (findSet(a) != findSet(b)) linkSets(findSet(a),findSet(b));
+}
+
+void getSize(int i) {
+	return -unions[findSet(i)];
 }