diff options
| -rw-r--r-- | other/other.tex | 25 | ||||
| -rw-r--r-- | tcr.pdf | bin | 663594 -> 647740 bytes |
2 files changed, 17 insertions, 8 deletions
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} Binary files differ |