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
|
\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}{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}{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 >= $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}{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}
\clearpage
\begin{algorithm}{Lichao}
\sourcecode{datastructures/lichao.cpp}
\end{algorithm}
\begin{algorithm}{Policy Based Data Structures}
\textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}!
\sourcecode{datastructures/stlPriorityQueue.cpp}
\columnbreak
\sourcecode{datastructures/pbds.cpp}
\end{algorithm}
\begin{algorithm}{Lower/Upper 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.
\sourcecode{datastructures/monotonicConvexHull.cpp}
\sourcecode{datastructures/dynamicConvexHull.cpp}
\end{algorithm}
\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}
\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}
\begin{algorithm}[optional]{Range Minimum Query}
\begin{methods}
\method{init}{baut Struktur auf}{n\*\log(n)}
\method{query}{Index des Minimums in [l, r)}{1}
\end{methods}
\sourcecode{datastructures/RMQ.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}
|
