From d6d3b6183df2e1d40154f406916993f9b15b3cae Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Sun, 28 Apr 2024 03:26:45 +0200
Subject: improve sparse tables

---
 datastructures/test/sparseTable.cpp         | 24 ++++++++++++++++++++++++
 datastructures/test/sparseTableDisjoint.cpp | 24 ++++++++++++++++++++++++
 2 files changed, 48 insertions(+)
 create mode 100644 datastructures/test/sparseTable.cpp
 create mode 100644 datastructures/test/sparseTableDisjoint.cpp

(limited to 'datastructures/test')

diff --git a/datastructures/test/sparseTable.cpp b/datastructures/test/sparseTable.cpp
new file mode 100644
index 0000000..ed4d61f
--- /dev/null
+++ b/datastructures/test/sparseTable.cpp
@@ -0,0 +1,24 @@
+#include "../sparseTable.cpp"
+
+void test(int n) {
+	vector<ll> values(n);
+	for (ll &x: values) x = util::randint();
+	SparseTable st;
+	st.init(values);
+	for (int i = 0; i < n; i++) {
+		int l = util::randint(n);
+		int r = util::randint(n);
+		if (l > r) swap(l, r);
+		r++;
+		assert(
+			values[st.queryIdempotent(l, r)]
+			==
+			*min_element(values.begin()+l, values.begin()+r)
+		);
+	}
+}
+
+int main() {
+	test(1000);
+	test(1);
+}
diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp
new file mode 100644
index 0000000..43c6d6e
--- /dev/null
+++ b/datastructures/test/sparseTableDisjoint.cpp
@@ -0,0 +1,24 @@
+#include "../sparseTableDisjoint.cpp"
+
+void test(int n) {
+	vector<ll> values(n);
+	for (ll &x: values) x = util::randint();
+	DisjointST st;
+	st.init(values);
+	for (int i = 0; i < n; i++) {
+		int l = util::randint(n);
+		int r = util::randint(n);
+		if (l > r) swap(l, r);
+		r++;
+		assert(
+			st.query(l, r)
+			==
+			accumulate(values.begin()+l, values.begin()+r, 0ll)
+		);
+	}
+}
+
+int main() {
+	test(1000);
+	test(1);
+}
-- 
cgit v1.2.3