From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

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

(limited to 'datastructures/RMQ.cpp')

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
new file mode 100644
index 0000000..b38b838
--- /dev/null
+++ b/datastructures/RMQ.cpp
@@ -0,0 +1,27 @@
+vector<int> values;
+vector<vector<int>> rmq;
+
+int select(int a, int b) {
+	return values[a] <= values[b] ? a : b;
+}
+
+void build() {
+	for(int i = 0, s = 1, ss = 1; s <= values.size(); ss=s, s*=2, i++) {
+		for(int l = 0; l + s <= values.size(); l++) {
+			if(i == 0) rmq[0][l] = l;
+			else {
+				int r = l + ss;
+				rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]);
+}}}}
+
+void init(vector<int>& v) {
+	values = v;
+	rmq = vector<vector<int>>(floor(log2(values.size()))+1, vector<int>(values.size()));
+	build();
+}
+
+int query(int l, int r) {
+	if(l >= r) return l;
+	int s = floor(log2(r-l)); r = r - (1 << s);
+	return select(rmq[s][l],rmq[s][r]);
+}
\ No newline at end of file
-- 
cgit v1.2.3