From a8a6d218ec928d2d85268e3334fe80c55cb4b603 Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Fri, 17 Feb 2023 11:51:41 +0100
Subject: added some SQRT techniques

---
 other/other.tex | 25 +++++++++++++++++--------
 1 file changed, 17 insertions(+), 8 deletions(-)

(limited to 'other/other.tex')

diff --git a/other/other.tex b/other/other.tex
index 1097dc3..a6add20 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -215,14 +215,6 @@
 	Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig:
 	\[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\]
 	
-	\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:~\runtime{n\cdot\sqrt{n}}.
-	(Anzahl der Blöcke als Konstante in Code schreiben.)
-	
 	\item \textbf{Centroids of a Tree:}
 	Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted.
 	Es kann $2$ Centroids geben!
@@ -235,6 +227,23 @@
 	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}
 	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von
 	$\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern.
+	
+	\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:~\runtime{n\cdot\sqrt{n}}.
+	(Anzahl der Blöcke als Konstante in Code schreiben.)
+	
+	\item \textbf{SQRT Techniques:}
+	\begin{itemize}
+		\item Aufteilen in \emph{leichte} (wert $\leq\sqrt{x}$) und \emph{schwere} (höchsten $\sqrt{x}$ viele) Objekte.
+		\item Datenstruktur in Blöcke fester Größe (z.b. 256 oder 512) aufteilen.
+		\item Datenstruktur nach fester Anzahl Updates komplett neu bauen.
+		\item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{X}$ verschiedene werte von $x_i$.
+		\item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min{w,h}\leq\sqrt{X}$.
+	\end{itemize}
 \end{itemize}
 
 \subsection{Tipps \& Tricks}
-- 
cgit v1.2.3

