summaryrefslogtreecommitdiff
path: root/datastructures/sparseTableDisjoint.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures/sparseTableDisjoint.cpp')
-rw-r--r--datastructures/sparseTableDisjoint.cpp26
1 files changed, 0 insertions, 26 deletions
diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp
deleted file mode 100644
index dc5297a..0000000
--- a/datastructures/sparseTableDisjoint.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-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[i]);
- for (int i = min(n, c); i > c - l; i--)
- dst[h][i - 1] = combine(vec[i - 1], dst[h][i]);
- }}}
-
- ll query(int l, int r) {
- int h = __lg(l ^ r);
- return combine(dst[h][l], dst[h][r]);
- }
-};