content/datastructures/sparseTableDisjoint.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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) {
		if (r <= l) return neutral;
		int h = __lg(l ^ r);
		return combine(dst[h][l], dst[h][r]);
	}
};