From 7e24d9d392aff890981f13c299b283189d94a75d Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Fri, 15 Mar 2024 01:25:09 +0100
Subject: too many changes for one commit

- simplify envelope code
- add more files as optional
- allow compiling optional without editing tcr.tex
- formatting changes
---
 datastructures/datastructures.tex | 43 +++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

(limited to 'datastructures/datastructures.tex')

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}
 
-- 
cgit v1.2.3

