1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
\section{Datenstrukturen}
\begin{algorithm}{Segmentbaum}
\begin{methods}
\method{SegTree}{baut den Baum auf}{n}
\method{query}{findet Summe über $[l, r)$}{\log(n)}
\method{update}{ändert einen Wert}{\log(n)}
\end{methods}
\sourcecode{datastructures/segmentTree.cpp}
\subsubsection{Lazy Propagation}
Assignment modifications, sum queries \\
\method{binary\_search}{kleinstes $x$ in $[l, r]$ mit $f(\text{query}(l, x))$ (monoton in $x$)}{\log(n)}
\sourcecode{datastructures/lazyPropagation.cpp}
\end{algorithm}
\begin{algorithm}{Wavelet Tree}
\begin{methods}
\method{WaveletTree}{baut den Baum auf}{n\*\log(\Sigma)}
\method{kth}{sort $[l, r)[k]$}{\log(\Sigma)}
\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)}
\end{methods}
$\Sigma$ ist die Gr\"o\ss e des Eingabebereichs, d.h.
$\mathit{max} - \mathit{min}$.
\sourcecode{datastructures/waveletTree.cpp}
\end{algorithm}
\columnbreak
\begin{algorithm}{Fenwick Tree}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
\method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
\method{update}{addiert ein Delta zu einem Element}{\log(n)}
\end{methods}
\sourcecode{datastructures/fenwickTree.cpp}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
\method{prefix\_sum}{summe von $[0, i)$}{\log(n)}
\method{update}{addiert ein Delta zu allen Elementen $[l, r)$}{\log(n)}
\end{methods}
\sourcecode{datastructures/fenwickTree2.cpp}
\end{algorithm}
\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
\sourcecode{datastructures/stlRope.cpp}
\end{algorithm}
\columnbreak
\begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
\begin{methods}
\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)}
\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
\end{methods}
\sourcecode{datastructures/treap.cpp}
\end{algorithm}
\begin{algorithm}{Range Minimum Query}
\begin{methods}
\method{init}{baut Struktur auf}{n\*\log(n)}
\method{query}{Index des Minimums in $[l, r)$}{1}
\end{methods}
\begin{itemize}
\item \code{better}-Funktion muss idempotent sein!
\end{itemize}
\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}{STL-Bitset}
\sourcecode{datastructures/bitset.cpp}
\end{algorithm}
\begin{algorithm}{Link/Cut Tree}
\begin{methods}
\method{LCT}{baut Wald auf}{n}
\method{connected}{prüft ob zwei Knoten im selben Baum liegen}{\log(n)}
\method{link}{fügt $\{x,y\}$ Kante ein}{\log(n)}
\method{cut}{entfernt $\{x,y\}$ Kante}{\log(n)}
\method{lca}{berechnet LCA von $x$ und $y$}{\log(n)}
\method{query}{berechnet \code{query} auf den Knoten des $xy$-Pfades}{\log(n)}
\method{modify}{erhöht jeden wert auf dem $xy$-Pfad}{\log(n)}
\end{methods}
\sourcecode{datastructures/LCT.cpp}
\end{algorithm}
\columnbreak
\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}
\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}
\subsubsection{Li Chao Tree}
Every pair of functions has at most one intersection.
\begin{methods}
\method{insert}{add function}{\log(|xs|)}
\method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)}
\end{methods}
\sourcecode{datastructures/lichao.cpp}
\end{algorithm}
\begin{algorithm}{Policy Based Data Structures}
\sourcecode{datastructures/pbds.cpp}
\end{algorithm}
\begin{algorithm}{Union-Find}
\begin{methods}
\method{UnionFind}{legt $n$ einzelne Elemente an}{n}
\method{find}{findet den Repräsentanten}{\log(n)}
\method{link}{vereint 2 Mengen}{\log(n)}
\method{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)}
\method{add}{fügt neues einzelnes Element ein}{1}
\method{m\*find + n\*link}{Folge von Befehlen}{n+m\*\alpha(n)}
\end{methods}
\sourcecode{datastructures/unionFind.cpp}
\end{algorithm}
\columnbreak
\begin{algorithm}{Persistent}
\begin{methods}
\method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)}
\method{set}{ändert Wert zu Zeitpunkt $t$}{\log(t)}
\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
\end{methods}
\sourcecode{datastructures/persistent.cpp}
\sourcecode{datastructures/persistentArray.cpp}
\end{algorithm}
|
