improve sparse tables

1 files changed, 24 insertions, 0 deletions

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);
+}