diff options
| -rw-r--r-- | datastructures/datastructures.tex | 4 | ||||
| -rw-r--r-- | datastructures/sparseTable.cpp | 27 | ||||
| -rw-r--r-- | graph/LCA.cpp | 21 | ||||
| -rw-r--r-- | graph/graph.tex | 2 | ||||
| -rw-r--r-- | graph/lca.cpp | 28 | ||||
| -rw-r--r-- | tcr.pdf | bin | 323512 -> 323838 bytes |
6 files changed, 58 insertions, 24 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 87d2a6d..b3683bf 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -13,8 +13,8 @@ \lstinputlisting{datastructures/fenwickTree.cpp} \lstinputlisting{datastructures/fenwickTreeNiklas.cpp} -\subsection{Range Minimum Query} -\lstinputlisting{datastructures/RMQ.cpp} +\subsection{Sparse Table} +\lstinputlisting{datastructures/sparseTable.cpp} \subsection{STL-Tree} \lstinputlisting{datastructures/stlTree.cpp} diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp new file mode 100644 index 0000000..52867de --- /dev/null +++ b/datastructures/sparseTable.cpp @@ -0,0 +1,27 @@ +struct SparseTable { + int st[MAX_N][MAX_LOG + 1], log[MAX_N + 1]; // Achtung: 2^MAX_LOG > MAX_N + vector<int> *a; + + // Funktion muss idempotent sein! Hier Minimum. + bool better(int lidx, int ridx) { return a->at(lidx) <= a->at(ridx); } + + void init(vector<int> *vec) { + a = vec; + for (int i = 0; i < (int)a->size(); i++) st[i][0] = i; + for (int j = 1; j <= MAX_LOG; j++) { + for (int i = 0; i + (1 << j) <= (int)a->size(); i++) { + st[i][j] = better(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]) + ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1]; + }} + + log[1] = 0; + for (int i = 2; i <= MAX_N; i++) log[i] = log[i/2] + 1; + } + + // Gibt Index des Ergebnisses in [l,r]. Laufzeit: O(1) + int queryIdempotent(int l, int r) { + int j = log[r - l + 1]; + return better(st[l][j], st[r - (1 << j) + 1][j]) + ? st[l][j] : st[r - (1 << j) + 1][j]; + } +}; diff --git a/graph/LCA.cpp b/graph/LCA.cpp deleted file mode 100644 index c79cc5c..0000000 --- a/graph/LCA.cpp +++ /dev/null @@ -1,21 +0,0 @@ -vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); -vector<vector<int>> graph(MAX_N); - -// Funktioniert nur mit von der Wurzel weggerichteten Kanten. -// Falls ungerichtete Kanten, visited-check einführen. -void initLCA(int gi, int d, int &c) { // Laufzeit: O(n) - visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; - for(int gn : graph[gi]) { - initLCA(gn, d+1, c); - visited[c] = gi, depth[c] = d, c++; -}} - -int getLCA(int a, int b) { // Laufzeit: O(1) - return visited[queryRMQ( - min(first[a], first[b]), max(first[a], first[b]))]; -} - -// Benutzung: -int c = 0; -initLCA(0, 0, c); -initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth. diff --git a/graph/graph.tex b/graph/graph.tex index 7b901f9..37356f6 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -58,7 +58,7 @@ VISIT(v): \lstinputlisting{graph/euler.cpp} \subsection{Lowest Common Ancestor} -\lstinputlisting{graph/LCA.cpp} +\lstinputlisting{graph/lca.cpp} \subsection{Max-Flow} diff --git a/graph/lca.cpp b/graph/lca.cpp new file mode 100644 index 0000000..d6548e9 --- /dev/null +++ b/graph/lca.cpp @@ -0,0 +1,28 @@ +struct LCA { + vector<int> depth, visited, first; + int idx; + SparseTable st; + + void init(vector<vector<int>> &g, int root) { // Laufzeit: O(|V|) + depth.assign(2 * g.size(), 0); + visited.assign(2 * g.size(), -1); + first.assign(g.size(), 2 * g.size()); + idx = 0; + visit(g, root, 0); + st.init(&depth); + } + + void visit(vector<vector<int>> &g, int v, int d) { + visited[idx] = v, depth[idx] = d, first[v] = min(idx, first[v]), idx++; + + for (int w : g[v]) { + if (first[w] == 2 * (int)g.size()) { + visit(g, w, d + 1); + visited[idx] = v, depth[idx] = d, idx++; + }}} + + int getLCA(int a, int b) { // Laufzeit: O(1) + if (first[a] > first[b]) swap(a, b); + return visited[st.queryIdempotent(first[a], first[b])]; + } +}; Binary files differ |