Adding new code for sparse table implementation and LCA.

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])];
+  }
+};
diff --git a/tcr.pdf b/tcr.pdf
index 725e698..5fff6e7 100644
--- a/tcr.pdf
+++ b/tcr.pdf