add binary lifting and make old LCA optional

1 files changed, 11 insertions, 1 deletions

diff --git a/graph/graph.tex b/graph/graph.tex
index 6fbdb74..b251278 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -15,7 +15,7 @@
 	\end{itemize}
 \end{algorithm}
 
-\begin{algorithm}{Lowest Common Ancestor}
+\begin{algorithm}[optional]{Lowest Common Ancestor}
 	\begin{methods}
 		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
 		\method{getLCA}{findet LCA}{1}
@@ -24,6 +24,16 @@
 	\sourcecode{graph/LCA_sparse.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Binary Lifting}
+	\begin{methods}
+		\method{Lift}{constructor}{\abs{V}}
+		\method{depth}{distance to root of vertex $v$}{1}
+		\method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})}
+		\method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/binary_lifting.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Centroids}
 	\begin{methods}
 		\method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}}