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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
\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{lower\_bound}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)}
\sourcecode{datastructures/lazyPropagation.cpp}
\end{algorithm}
\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}
\columnbreak
\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
\sourcecode{datastructures/stlRope.cpp}
\end{algorithm}
\begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
\begin{methods}
\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen >= $i$)}{\log(n)}
\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
\end{methods}
\sourcecode{datastructures/treap2.cpp}
\end{algorithm}
\begin{algorithm}{Range Minimum Query}
\begin{methods}
\method{init}{baut Struktur auf}{n\*\log(n)}
\method{queryIdempotent}{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}{Wavelet Tree}
\begin{methods}
\method{Constructor}{baut den Baum auf}{n\*\log(n)}
\method{kth}{sort $[l, r)[k]$}{\log(n)}
\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
\end{methods}
\sourcecode{datastructures/waveletTree.cpp}
\end{algorithm}
\begin{algorithm}{STL-Bitset}
\sourcecode{datastructures/bitset.cpp}
\end{algorithm}
\begin{algorithm}{Link-Cut-Tree}
\begin{methods}
\method{Constructor}{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}{Union-Find}
\begin{methods}
\method{init}{legt $n$ einzelne Unions an}{n}
\method{findSet}{findet den Repräsentanten}{\log(n)}
\method{unionSets}{vereint 2 Mengen}{\log(n)}
\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
\end{methods}
\sourcecode{datastructures/unionFind.cpp}
\end{algorithm}
\begin{algorithm}[optional]{Union-Find with size}
\begin{methods}
\method{init}{legt $n$ einzelne Unions an}{n}
\method{findSet}{findet den Repräsentanten}{\log(n)}
\method{unionSets}{vereint 2 Mengen}{\log(n)}
\method{getSize}{zählt Elemente in Menge, die $i$ enthält}{\log(n)}
\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
\end{methods}
\sourcecode{datastructures/unionFind2.cpp}
\end{algorithm}
\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}
\columnbreak
\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}
\optional{
\subsubsection{Li Chao tree \opthint}
\sourcecode{datastructures/lichao.cpp}
}
\end{algorithm}
\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}
\columnbreak
\sourcecode{datastructures/persistentArray.cpp}
\end{algorithm}
\begin{algorithm}{STL-Tree}
\sourcecode{datastructures/stlTree.cpp}
\end{algorithm}
\begin{algorithm}{STL Priority Queue}
Nicht notwendig, wenn Smaller-Larger-Optimization greift.
\sourcecode{datastructures/stlPQ.cpp}
\end{algorithm}
\begin{algorithm}{STL HashMap}
3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
\sourcecode{datastructures/stlHashMap.cpp}
\end{algorithm}
\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
\begin{methods}
\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
\end{methods}
\sourcecode{datastructures/firstUnused.cpp}
\end{algorithm}
|
