From 7d443816db171b236a7c7e1cbdd87cf65b361d89 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Tue, 24 Oct 2017 21:45:22 +0200
Subject: Adding short description on Mo's Algorithm.

---
 other/other.tex | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

(limited to 'other/other.tex')

diff --git a/other/other.tex b/other/other.tex
index b275c6e..9dbc018 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -126,7 +126,15 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 	Berechnung: Maximales Matching in bipartitem Graphen.
 	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
 	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
-	Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. 
+	Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden.
+
+	\item \textbf{\textsc{Mo}'s Algorithm:}
+	SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$.
+	Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$.
+	Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$.
+	Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls.
+	Laufzeit:~$\mathcal{O}(n\cdot\sqrt{n})$.
+	(Anzahl der Blöcke als Konstante in Code schreiben.)
 \end{itemize}
 
 \subsection{Tipps \& Tricks}
-- 
cgit v1.2.3

