From 4905811a7c635f28827984a999aedacd910f4dc3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 29 Aug 2023 00:09:28 +0200
Subject: consistency

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

(limited to 'datastructures/sparseTableDisjoint.cpp')

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]);
+	}
+};
-- 
cgit v1.2.3