From 9753d518eb3204e380bdf4af24145166896bcf76 Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Sat, 22 Nov 2014 20:15:44 +0100
Subject: Create RMQ.cpp

---
 datastructures/RMQ.cpp | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)
 create mode 100644 datastructures/RMQ.cpp

(limited to 'datastructures')

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
new file mode 100644
index 0000000..899db15
--- /dev/null
+++ b/datastructures/RMQ.cpp
@@ -0,0 +1,20 @@
+vector<int> data(RMQ_SIZE);
+vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE));
+
+void initRMQ() {
+	for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) {
+		for(int l = 0; l + s <= RMQ_SIZE; l++) {
+			if(i == 0) rmq[0][l] = l;
+			else {
+				int r = l + ss;
+				rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]);
+			}
+		}
+	}
+}
+//returns index of minimum! [a, b)
+int queryRMQ(int l, int r) {
+	if(l >= r) return l;
+	int s = floor(log2(r-l)); r = r - (1 << s);
+	return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]);
+}
-- 
cgit v1.2.3


From 213662f659ed8b0a95da110ae6eb5e91e2ecae71 Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Sat, 22 Nov 2014 20:16:34 +0100
Subject: added RMQ.

---
 datastructures/datastructures.tex | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'datastructures')

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index c314400..baa4fec 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -5,3 +5,6 @@
 
 \subsection{Segmentbaum}
 \lstinputlisting{datastructures/segmentTree.cpp}
+
+\subsection{Range Minimum Query}
+\lstinputlisting{datastructures/RMQ.cpp}
-- 
cgit v1.2.3