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

---
 Makefile                                    |  7 +++++++
 datastructures/sparseTable.cpp              |  6 +++---
 datastructures/sparseTableDisjoint.cpp      | 12 ++++++------
 datastructures/test/sparseTable.cpp         | 24 ++++++++++++++++++++++++
 datastructures/test/sparseTableDisjoint.cpp | 24 ++++++++++++++++++++++++
 graph/LCA_sparse.cpp                        |  2 +-
 6 files changed, 65 insertions(+), 10 deletions(-)
 create mode 100644 datastructures/test/sparseTable.cpp
 create mode 100644 datastructures/test/sparseTableDisjoint.cpp

diff --git a/Makefile b/Makefile
index e3f59e6..160880f 100644
--- a/Makefile
+++ b/Makefile
@@ -3,6 +3,8 @@ TESTS = \
 	datastructures/test/fenwickTree2.test \
 	datastructures/test/monotonicConvexHull.test \
 	datastructures/test/persistent.test \
+	datastructures/test/sparseTable.test \
+	datastructures/test/sparseTableDisjoint.test \
 	graph/test/binary_lifting.test \
 	graph/test/LCA_sparse.test \
 	math/test/binomial0.test
@@ -47,6 +49,11 @@ datastructures/test/monotonicConvexHull.test: \
 	datastructures/monotonicConvexHull.cpp
 datastructures/test/persistent.test: datastructures/test/persistent.cpp \
 	datastructures/persistent.cpp
+datastructures/test/sparseTable.test: datastructures/test/sparseTable.cpp \
+	datastructures/sparseTable.cpp
+datastructures/test/sparseTableDisjoint.test: \
+	datastructures/test/sparseTableDisjoint.cpp \
+	datastructures/sparseTableDisjoint.cpp
 graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \
 	graph/binary_lifting.cpp graph/test/util.cpp
 graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
index 63cce48..64a892a 100644
--- a/datastructures/sparseTable.cpp
+++ b/datastructures/sparseTable.cpp
@@ -6,9 +6,9 @@ struct SparseTable {
 		return a[lidx] <= a[ridx] ? lidx : ridx;
 	}
 
-	void init(vector<ll> *vec) {
-		int n = sz(*vec);
-		a = vec->data();
+	void init(vector<ll> &vec) {
+		int n = sz(vec);
+		a = vec.data();
 		st.assign(__lg(n) + 1, vector<int>(n));
 		iota(all(st[0]), 0);
 		for (int j = 0; (2 << j) <= n; j++) {
diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp
index 31e9025..dc5297a 100644
--- a/datastructures/sparseTableDisjoint.cpp
+++ b/datastructures/sparseTableDisjoint.cpp
@@ -1,5 +1,5 @@
 struct DisjointST {
-	static constexpr ll neutral = 0
+	static constexpr ll neutral = 0;
 	vector<vector<ll>> dst;
 	ll* a;
 
@@ -7,16 +7,16 @@ struct DisjointST {
 		return x + y;
 	}
 
-	void init(vector<ll> *vec) {
-		int n = sz(*vec);
-		a = vec->data();
+	void init(vector<ll> &vec) {
+		int n = sz(vec);
+		a = vec.data();
 		dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral));
 		for (int h = 0, l = 1; l <= n; h++, l *= 2) {
 			for (int c = l; c < n + l; c += 2 * l) {
 				for (int i = c; i < min(n, c + l); i++)
-					dst[h][i + 1] = combine(dst[h][i], vec->at(i));
+					dst[h][i + 1] = combine(dst[h][i], vec[i]);
 				for (int i = min(n, c); i > c - l; i--)
-					dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]);
+					dst[h][i - 1] = combine(vec[i - 1], dst[h][i]);
 	}}}
 
 	ll query(int l, int r) {
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);
+}
diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp
index 0f2fe22..06b294f 100644
--- a/graph/LCA_sparse.cpp
+++ b/graph/LCA_sparse.cpp
@@ -10,7 +10,7 @@ struct LCA {
 		first.assign(sz(adj), 2 * sz(adj));
 		idx = 0;
 		dfs(adj, root);
-		st.init(&depth);
+		st.init(depth);
 	}
 
 	void dfs(vector<vector<int>>& adj, int v, ll d=0) {
-- 
cgit v1.2.3