consistency

2 files changed, 32 insertions, 5 deletions

diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
index 61a6802..7578695 100644
--- a/datastructures/sparseTable.cpp
+++ b/datastructures/sparseTable.cpp
@@ -3,15 +3,16 @@ struct SparseTable {
 	vector<ll> *a;
 
 	int better(int lidx, int ridx) {
-		return a->at(lidx) <= a->at(ridx) ? lidx : ridx;
+		return a[lidx] <= a[ridx] ? lidx : ridx;
 	}
 
 	void init(vector<ll> *vec) {
-		a = vec;
-		st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a)));
+		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) <= sz(*a); j++) {
-			for (int i = 0; i + (2 << j) <= sz(*a); i++) {
+		for (int j = 0; (2 << j) <= n; j++) {
+			for (int i = 0; i + (2 << j) <= n; i++) {
 				st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]);
 	}}}
 
diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp
new file mode 100644
index 0000000..31e9025
--- /dev/null
+++ b/datastructures/sparseTableDisjoint.cpp
@@ -0,0 +1,26 @@
+struct DisjointST {
+	static constexpr ll neutral = 0
+	vector<vector<ll>> dst;
+	ll* a;
+
+	ll combine(const ll& x, const ll& y) {
+		return x + y;
+	}
+
+	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));
+				for (int i = min(n, c); i > c - l; i--)
+					dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]);
+	}}}
+
+	ll query(int l, int r) {
+		int h = __lg(l ^ r);
+		return combine(dst[h][l], dst[h][r]);
+	}
+};