diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/datastructures.tex | 2 | ||||
| -rw-r--r-- | datastructures/segmentTree.cpp | 5 | ||||
| -rw-r--r-- | datastructures/unionFind.cpp | 16 |
3 files changed, 15 insertions, 8 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4f9ad04..7edb390 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,6 +5,8 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} +\lstinline{update()} kann so umgeschrieben werden, dass ganze Intervalle geändert werden. +Dazu muss ein Offset in den inneren Knoten des Baums gespeichert werden. \subsection{Range Minimum Query} \lstinputlisting{datastructures/RMQ.cpp} diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 14973fe..93a2ceb 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -1,8 +1,10 @@ +// Laufzeit: init: O(n), query: O(log n), update: O(log n) +// Berechnet das Maximum im Array. int a[MAX_N], m[4 * MAX_N]; int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) { if (x <= X && Y <= y) return m[k]; - if (y < X || Y < x) return -1000000000; //ein "neutrales" Element + if (y < X || Y < x) return -1000000000; // Ein "neutrales" Element. int M = (X + Y) / 2; return max(query(x, y, 2 * k + 1, X, M), query(x, y, 2 * k + 2, M + 1, Y)); } @@ -20,6 +22,7 @@ void update(int i, int v, int k = 0, int X = 0, int Y = MAX_N - 1) { m[k] = max(m[2 * k + 1], m[2 * k + 2]); } +// Einmal vor allen anderen Operationen aufrufen. void init(int k = 0, int X = 0, int Y = MAX_N - 1) { if (X == Y) { m[k] = a[X]; diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp index 1ee532c..4b13dbf 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,19 +1,21 @@ -vector<int> parent, rank2; //manche Compiler verbieten Variable mit Namen rank +// Laufzeit: O(n*alpha(n)) +// "size" ist obere Schranke für die Höhe der Bäume. +vector<int> parent, size; -int findSet(int n) { //Pfadkompression +int findSet(int n) { // Pfadkompression if (parent[n] != n) parent[n] = findSet(parent[n]); return parent[n]; } -void linkSets(int a, int b) { //union by rank - if (rank2[a] < rank2[b]) parent[a] = b; - else if (rank2[b] < rank2[a]) parent[b] = a; +void linkSets(int a, int b) { // Union by rank. + if (size[a] < size[b]) parent[a] = b; + else if (size[b] < size[a]) parent[b] = a; else { parent[a] = b; - rank2[b]++; + size[b]++; } } -void unionSets(int a, int b) { +void unionSets(int a, int b) { // Diese Funktion aufrufen. if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); } |