From 9facd3655e2b86799699a6fdbd566cb4b2a7fb1c Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Fri, 22 Dec 2017 12:49:35 +0100
Subject: Adding new code for sparse table implementation and LCA.

---
 datastructures/datastructures.tex |  4 ++--
 datastructures/sparseTable.cpp    | 27 +++++++++++++++++++++++++++
 2 files changed, 29 insertions(+), 2 deletions(-)
 create mode 100644 datastructures/sparseTable.cpp

(limited to 'datastructures')

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];
+  }
+};
-- 
cgit v1.2.3